• DocumentCode
    1149660
  • Title

    The Complexity of Horizontal Word Encoding in Microprogrammed Machines

  • Author

    Mueller, Robert A. ; Allan, Vicki H. ; Varghese, Joseph

  • Author_Institution
    Department of Computer Science, Colorado State University
  • Issue
    10
  • fYear
    1984
  • Firstpage
    938
  • Lastpage
    939
  • Abstract
    We consider the complexity of the problem of encoding microoperations into the fields of a control word on a horizontally microprogrammed machine, and show it to be NP-complete. The major result of this correspondence is a formalization of the microinstruction encoding problem, which makes the complexity argument straightforward.
  • Keywords
    Bit encodings; NP-completeness; horizontal microinstructions; microprogramming; Books; Compaction; Computer science; Encoding; Microprogramming; Polynomials; Bit encodings; NP-completeness; horizontal microinstructions; microprogramming;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1984.1676358
  • Filename
    1676358
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1149660