The optimization of read-only memory (ROM) digit dimension for microprogrammed digital computers is considered. The design of integrated injection logic (I2L) multiple valued ROMs is reviewed and designs for corresponding digit-line decoders are presented. Results are presented for determining microoperation groupings that achieve the lower bound digit dimension for multivalued encodings, thus extending to arbitrary radix the theory for the binary case. To illustrate the applicability of these results, the microprogram specifications for previously published optimization examples, as well as that for the Digital Equipment Corporation EDP-9, are shown to have optimal encodings using either three- or four-valued ROMs and either ternary- or quaternary-to-binary decoders, resulting in dramatic savings in device count for the control memory portion of the corresponding machine.

The``state'' of a sequential machine is interpreted as the sequence-to-sequence input-output mapping performed by the machine. Such mappings have been called sequential functions. This concept of state is applied to the theory of binary linear sequential machines. The modulo-2 adders are assumed to have an inherent delay td≥0, and the effects of initial conditions are considered. The pertinent results from the algebra of delay polynomials are summarized, and the state structure of linear sequential functions is outlined. It is shown that every retrospective linear sequential function can be realized using only unit-delay modulo-2 adders, and bounds are derived on the minimum realizable delay between input and output.