Coded data generation or conversion – Digital code to digital code converters – To or from minimum d.c. level codes
Reexamination Certificate
2002-05-28
2003-09-16
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from minimum d.c. level codes
C341S050000
Reexamination Certificate
active
06621427
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to techniques for transmitting data through electrical signals. More specifically, the present invention relates to a method and an apparatus for implementing a doubly balanced code, wherein each codeword has a substantially equal number of ones and zeros, and wherein each transition between codewords involves a substantially equal number of rising and falling transitions.
2. Related Art
As processor clock speeds continue to increase at an exponential rate, data must be transferred at correspondingly faster rates between computer system components. Computer systems typically use large parallel busses for this purpose.
These large parallel busses typically use either single-ended signaling or differential signaling. Single-ended signaling makes use of a single signal line to carry each bit, along with one or more clock lines to latch the signals.
In contrast, differential signaling uses two signal lines to carry each bit, wherein the value of the bit is indicated by a voltage difference between the two signal lines. Because currents are balanced between power and ground rails, differential signaling reduces power supply noise and solves the problem of where return currents come from. Moreover, differential signaling is less sensitive to ground shifts between sender and receiver because differential signaling relies on voltage differences between pairs of signal lines, instead of relying on an absolute voltage level of a single signal line.
Unfortunately, differential signaling uses twice as many wires as single-ended signaling, which can greatly exacerbate pin limitation problems.
What is needed is a method and apparatus for transferring data between computer system components without the large number of signal lines required by differential signaling, and without the current balance and ground noise problems of single-ended signaling.
SUMMARY
One embodiment of the present invention provides a system for encoding a dataword into a current codeword within a stream of codewords, wherein each codeword in the stream has a substantially equal number of ones and zeros, and wherein each transition between codewords involves a substantially equal number of rising and falling transitions. The system creates the current codeword from the dataword and a preceding codeword in the stream by inverting substantially half of the zero bits of the preceding codeword and inverting substantially half of the one bits of the preceding codeword. This is accomplished by using the dataword to select one bits and the zero bits to invert; determining locations of the one bits and zero bits in the preceding codeword; and then inverting the selected one bits and zero bits in the preceding codeword to form the current codeword. Note that because the present invention balances rising and falling transitions without significantly increasing pin requirements, it achieves most of the electrical advantages of differential signaling along with most of the pin-efficiency of single-ended signaling. Moreover, by having substantially half the bits change at each transition, it is possible to determine timing information from transitions in the codeword, without the need for a separate clock signal.
In a variation on this embodiment, there exists a predefined mapping between possible bit patterns for the dataword and corresponding inversion patterns for zero bits in the preceding codeword. There also exists a predefined mapping between possible bit patterns for the dataword and corresponding inversion patterns for one bits in the preceding codeword.
In a variation on this embodiment, the system divides the dataword into a first index and a second index. The system uses the first index to identify zero bits of the preceding codeword to invert, and uses the second index to identify one bits of the preceding codeword to invert.
In a variation on this embodiment, using the first index to identify zero bits of the preceding codeword to invert involves using the first index to perform a lookup into a first table containing inversion patterns for zero bits of the preceding Moreover, using the second index to identify one bits of the preceding codeword to invert involves using the second index to perform a lookup into a second table containing inversion patterns for one bits of the preceding codeword.
In a variation on this embodiment, determining locations of the one bits and zero bits in the preceding codeword involves using a prefix sum calculation circuit to identify locations of zero bits and one bits in the preceding codeword.
In a variation on this embodiment, inverting the selected one bits and zero bits in the preceding codeword involves using a selection circuit for each bit in the preceding codeword to select a corresponding inversion bit based on an index for the bit generated by the prefix sum calculation circuit.
One embodiment of the present invention provides a system for decoding a codeword into a data word. During operation, the system receives a stream of codewords, including a preceding codeword and the current codeword, wherein each codeword in the stream has a substantially equal number of ones and zeros, and wherein each transition between codewords involves a substantially equal number of rising and falling transitions. Next, the system identifies a pattern of bits that have been inverted in the preceding codeword to produce the current codeword, and translates this pattern into the data word, wherein the translation uses a predefined mapping between inversion patterns for bits in the preceding codeword and bit patterns for the data word.
In a variation on this embodiment, the system identifies a pattern of zero bits that have been inverted in the preceding codeword to produce the current codeword, and also identifies a pattern of one bits that have been inverted in the preceding codeword to produce the current codeword. In this embodiment, the system translates the pattern of zero bits into a first part of the data word by using a predefined mapping between inversion patterns for zero bits in the preceding codeword and bit patterns for the first part of the data word. The system also translates the pattern of one bits into a second part of the data word by using a predefined mapping between inversion patterns for one bits in the preceding codeword and bit patterns for the second part of the data word.
In a variation on this embodiment, the system identifies the pattern of one bits and the pattern of zero bits by producing a permutation that sorts the preceding codeword so that: zeros and ones are separated; relative ordering is maintained between ones; and relative ordering is maintained between zeros. Next, the system permutes the current codeword using the permutation, so that a first part of the permuted codeword contains the pattern of zero bits in the preceding codeword have been inverted, and a second part of the permuted codeword contains the pattern of one bits in the preceding codeword have been inverted. In a variation on this embodiment, this permutation is produced by using a sorting network.
In a variation on this embodiment, the system uses the pattern of zero bits to perform a lookup into a first table containing corresponding bit patterns for the first part of the data word. The system also uses the pattern of one bits to perform a lookup into a second table containing corresponding bit patterns for the second part of the data word.
REFERENCES:
patent: 6241778 (2001-06-01), de Lind van Wijngaarden et al.
patent: 6489900 (2002-12-01), Shin et al.
Nguyen Khai
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Young Brian
LandOfFree
Method and apparatus for implementing a doubly balanced code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing a doubly balanced code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing a doubly balanced code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016577