Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-31
2003-07-22
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S265000
Reexamination Certificate
active
06598205
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and a method for decoding input signal samples in a high-speed communication system. More particularly, the invention relates to a system and a method for decoding the trellis code specified in the IEEE 802.ab standard for Gigabit Ethernet (also termed 1000BASE-T standard).
2. Description of the Related Art
Convolutional encoding and Viterbi decoding are used to provide forward error correction in transmitted digital data, and thus improve digital communication performance over a given noisy channel. The convolutional encoder establishes a code-tree relationship between input and output sequences. Each branch of the tree represents a single input symbol. Any input sequence traces out a specific path through the tree. Another way of viewing the code tree is the trellis diagram.
The Viterbi algorithm attempts to find a path through the trellis using the maximum likelihood decision. The two paths entering each node of a trellis are compared, and the path with the best metric (minimum error) is selected. The other path is rejected since its likelihood can never exceed that of the selected path regardless of the subsequent received data. Thus, at any giver time, there is only one path with the best metric entering into each current node of the trellis.
A Viterbi decoder is a maximum likelihood decoder that provides a forward error correction. Viterbi decoding is used in decoding a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in telecommunication transmission through various media with each set of bits representing a symbol instant.
In the decoding process, the Viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which bit sequence has most likely been transmitted. The possible transitions from a bit at one symbol instant, or state, to a bit at a next, subsequent, symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and defined as a branch. A sequence of interconnected branches defines a path.
Each state can only transit to a limited number of next states upon receiving a next bit in the bit stream. Thus, some paths survive during the decoding process and other paths do not. By eliminating those transition paths that are not permissible, computational efficiency can be improved in determining those paths most likely to survive. The Viterbi decoder typically defines and calculates a branch metric associated with each branch and employs this branch metric to determine which paths will survive and which paths will not.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric, an accumulated cost, that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is obtained by selecting a smaller one of the sums of the branch metrics for different possible transitions and the path metrics at the previous states.
While several paths survive the transition from one symbol instant to a next symbol instant, there is only one minimum accumulated cost path. A sequence of symbol instants tracing back through the trellis that extends a path with the minimum accumulated cost defines the length, or decoding depth D, of a trace-back. The individual state in the trellis associated with the minimum accumulated cost in a trace-back is translated into a most likely data to have been transmitted in that symbol instant. The data is referred to as a decoded symbol.
By using convolutional codes, a large coding gain can be obtained for a large memory or, equivalently, a long constraint length. The complexity of a maximum likelihood decoder is approximately proportional to the number of states, and, using existing design methodologies, can grow exponentially with symbol length and, thus, memory size. This increased size and complexity comes at the cost of substantially increased power requirements, and large device area requirements for high-precision signal processing.
What is needed is a system and a method that makes it possible for a significant reduction in size and complexity of a maximum likelihood decoder which likewise affords substantially reduced power requirements for a given application.
SUMMARY OF THE INVENTION
The present invention meets the aforementioned needs for reducing the size, complexity, and power consumption of decoders, and associated transceivers and communication systems, by providing a memory structure which receives and stores undecoded symbols, with each of the undecoded symbols having a unique pointer associated therewith. One of the undecoded symbols is a most likely symbol. The present invention selects the most likely symbol using a pointer selector which processes the unique pointers according to a predetermined selection operation, for example, a shuffle-exchange operation, and selects the most likely pointer which, in turn, is uniquely associated with the most likely symbol. The most likely pointer then is used to produce the most likely symbol, the decoder outputting the most likely symbol thereby. The present invention can be used in systems that conform to IEEE Standard 802.3ab, e.g., gigabit Ethernet systems.
The memory structure and pointer selector can be constituent of a maximum likelihood decoder, for example a trellis decoder, more specifically a Viterbi decoder. One such pointer selector is a shuffle exchange network which selects the most likely pointer using a shuffle exchange operation upon the pointers and not the potential symbols, as with previous architectures and methods.
In a particular embodiment, the present invention is implemented in a survivor memory unit which includes the memory structure and the shuffle exchange network. The memory structure can be a dual-port RAM FIFO, but also can be a single-port RAM, or even a DRAM, provided the device is capable of a read/modify/write operation within a single clock cycle.
The present invention is contemplated for use in gigabit Ethernet systems, transceivers, and decoders where 4-D symbols are used and the potential symbols are constrained to eight possible symbol states.
Also, the invention herein contemplates a method for symbolic communication, for example, using the IEEE Standard 802.3ab, which includes receiving potential symbols including a most likely symbol, associating each of the received potential symbols with a unique pointer, processing the unique pointers to determine a most likely pointer using a predetermined selection operation, and selecting the most likely symbol using the most likely pointer.
REFERENCES:
patent: 4748626 (1988-05-01), Wong
patent: 4823346 (1989-04-01), Kobayashi et al.
patent: 5379306 (1995-01-01), Noma et al.
patent: 5410555 (1995-04-01), Itakura et al.
patent: 5457705 (1995-10-01), Todoroki
patent: 5509021 (1996-04-01), Todoroki
patent: 5651032 (1997-07-01), Okita
patent: 5717706 (1998-02-01), Ikeda
patent: 5841819 (1998-11-01), Hu et al.
patent: 5881074 (1999-03-01), Rao
patent: 5946361 (1999-08-01), Araki et al.
patent: 6205187 (2001-03-01), Westfall
patent: 6289487 (2001-09-01), Hessel et al.
Kirkland et al., “High-Speed Viterbi Decoder Memory Design”, Can. J. Elect. & Comp. Eng., vol. 15, No. 3, 1990, pp. 107-114.*
Lee, Convolutional Coding: Fundamentals and Applications, Artech House, 1997, pp. 154-185.*
Casseau et al., “Architecture of a High-Rate VLSI Viterbi Decoder”, 1996 ICECS, pp. 21-24.*
Horowitz et al., “The Art of Electronics”, Cambridge University Press, 1989, p. 527-528.*
Mehdi Hatamian et al., Design Considerations for Gigabit Ethernet 100Base-Twisted Pair Transceivers, IEEE 1998 Custom Integrated Circuits Conference, 15.1.1-15.1.8.
E. Paaske et al., An Area-Efficient Path Memory Structure for VLSI Implementation of High Speed Viterbi Decoders, Integration, the VLSI Journal 12 (1991), 79-91.
Baker Stephen M.
Broadcom Corporation
McAndrews Held & Malloy Ltd.
LandOfFree
Memory-based shuffle-exchange traceback for gigabit ethernet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory-based shuffle-exchange traceback for gigabit ethernet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory-based shuffle-exchange traceback for gigabit ethernet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089029