Coded data generation or conversion – Digital code to digital code converters – To or from minimum d.c. level codes
Reexamination Certificate
2000-12-27
2003-12-09
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from minimum d.c. level codes
C714S018000, C365S200000, C341S095000
Reexamination Certificate
active
06661355
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of information transmission systems. More particularly, in one implementation, the present invention relates to constant-weight encoding and decoding of data words on a parallel data line bus.
BACKGROUND OF THE INVENTION
It is often desirable, in information transmission systems, to transform information into alternate forms. In one instance, a desirable form might be to encode data, to achieve a constant weight code, where each data word contained a constant number of data elements in each logic state. The data words could be binary words occupying two logic states, those of zero and one. This transformation enables the higher supply potential, Vdd, and the lower supply potential, Vss, to maintain constant current to the circuits that drive the signal lines and or constant current in the termination circuit, Vterm. In another instance it may be desirable to spread information from a data word into sub-words and the weight of the sub-words, where the weight of the sub-word is defined to be the number of data elements in each logic state. In a binary system the weight is the number of ones or zeros in a data word. In another instance it may be desirable to minimize the weight so that the power required to drive the parallel data line bus is minimized.
Transmission of N-ary data, where there are more than the traditional two logic states of zero and one, does not impose the same constant weight criterion that is imposed on binary data in order to achieve the constant current conditions mentioned above. There are many combinations of N-ary weight vectors that provide the desired constant current state.
Transmission of binary information on a parallel line bus requires the transmission of data words whose weight ranges from zero to the number of bits in the information word. Therefore, an eight-bit data word has a weight that ranges between zero and eight. Transmission of variable weight data presents problems to interconnect circuits, such as those used in a high-speed bus interface.
In a single-ended parallel interface with line drivers, transmission of variable weight data creates a data-dependent current flow in the Vdd and Vss connections. This data-dependent current flow leads to timing losses. Vdd and Vss interconnect path inductances (L) exist between the voltage sources and the line driver higher and lower potential bias nodes, respectively. A changing current in this inductance path (di/dt) creates voltage variation according to v=Ldi/dt. These voltage changes compromise the integrity of the output signals as a function of data word value. Specifically, they delay high to low and low to high transitions of the signal lines (edges) and create uncertainty in edge location. Both of these effects compromise achievable system speeds. The larger Ldi/dt the greater the degree of the timing loss. If all lines change at once, or if more lines are present di/dt is increases.
Path inductances (L) due to controllable design parameters is already at practical minimal limits. Differential architecture eliminates timing losses due to Vdd and Vss fluctuations, however, this comes at the expense of two lines per bit of information transmitted. It is desirable to obtain differential performance from single-ended architecture. Accordingly, constant-weight parallel encoding has been employed.
Constant-weight parallel encoding can achieve constant Vdd and Vss current flow at the expense of a slight increase in the bus line count. It is possible to achieve many of the benefits of a differential system with only a small increase in lines over single-ended architecture. We will define constant weight parallel encoding to be the result of encoding a data word into an encoded data word with a constant number of data elements in each logic state independent of the input data word value. We further define balanced encoding to be constant-weight parallel encoding such that the number of data elements in each logic state is the same. Thus, a balanced 22-bit encoded data word would have 11 data element whose value was zero and 11 data elements whose value was one. An almost balanced parallel-encoded data word would be closer to the balanced case than the unbalanced case.
As the data word length increases, the complexity of the encode process greatly increases the corresponding time to encode. To employ constant weight parallel encoding in a data transmission system, without compromising performance, requires efficient low latency coding methods. Design of efficient, low latency encoding/decoding methods has been an area of research for the past four decades. Attempts at solving this problem exist in the prior art.
Tallini, G., et. al., “Design of Balanced and Constant Weight Codes for VLSI Systems,” IEEE, vol. 47 no. 5, Transactions on Computers May (1998) describes encoding techniques applied to the input word as a whole without partitioning the input word into sub-words. Computation time to encode over an entire word is much greater than the computation time to encode a sub-word, such undivided approaches result in high complexity encode functions. These techniques remain complex and are not easily reduced to low latency implementations on an integrated circuit chip. Burleson, W., et. al., “Bus-Invert Coding for Low-Power I/O,” IEEE, vol. 3, no. 1, Transactions on Very Large Scale Integrations (VLSI) Systems March (1995) describes an inversion method for encoding that divides the input word up into sub-words and then proceeds to encode the sub-words to minimize the variability in the weight. Tabor, J., “Noise Reduction Using Low Weight And Constant Weight Coding Techniques,” MS Thesis, Artificial Intelligence Lab, MIT, May (1990) also describes dividing the input word into sub-words, but does not achieve constant weight encoding.
The prior-art techniques provide limited simplification of the problem. The prior-art techniques do not provide for sharing of information between sub-words or sub-word paths. Thus, it is desirable to provide efficient, low latency, encoding/decoding methodology that can be implemented with a minimum number of extra lines and encode/decode logic by sharing information between sub-words or sub-word paths to facilitate spreading information into the encoded sub-words as well as into the weight of the encoded sub-words.
SUMMARY OF THE INVENTION
The present invention includes methods for spreading and concentrating information into encoded data sub-words and the weight of the encoded data sub-words. An embodiment of the present invention is directed to efficient apparatus and methods for constant-weight encoding of data that can be implemented with low latency in a data transmission system. Various embodiments of the present invention are described below.
A method including dividing a data word into data sub-words onto sub-word paths; allowing communication between the sub-word paths; and encoding the data sub-words into encoded data sub-words; such that the information content of the data word is spread between the encoded data sub-words and the weight of the encoded data sub-words.
Another method includes: allowing communication between sub-word paths; and decoding encoded data sub-words into data sub-words; such that the data sub-words form a data word whereby the information content of the data word is concentrated back into the data word.
A preferred embodiment, of the present invention, includes a method of encoding a data word, whose data elements occupy at least a first logic state and a second logic state, the method includes: receiving data sub-words onto sub-word paths, the data sub-words comprising sets of data elements of the data word; and encoding the data sub-words into encoded data sub-words; such that the encoded data sub-words form an encoded data word wherein the information content of the data word is spread between the encoded data sub-words and the weight of the encoded data sub-words.
Another embodiment, of the present invention, includes an encoder module, to encode a data word, w
Athas William C.
Cornelius William P.
Apple Computer Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Jeanglaude Jean Bruner
LandOfFree
Methods and apparatus for constant-weight encoding &... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for constant-weight encoding &..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for constant-weight encoding &... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170938