Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-01-28
2003-05-06
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06560749
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to communication techniques and, more particularly, to the decoding of digital signals in a communication system. In the communication system envisioned by the present invention, each bit of information has been encoded in a multiplicity of transmitted signals. The resulting signals are generally referred to as convolutionally encoded symbols.
2. Description of the Related Art
Communications channels in general and digital wireless communications in particular must counteract noise which may obliterate individual transmitted symbols. Conceptually, there are two approaches to this problem: one, by introducing redundancy and another, by smearing the transmitted information over multiple symbols. These approaches are not entirely separate since any redundancy makes it easier to spread the information over a plurality of signals, but neither are the two approaches identical.
Convolution codes are often used to implement the smearing of information over several symbols. Simply put, the EXCLUSIVE_OR (XOR) logic operation is applied to several recent information bits (equivalently, the information bits are summed modulo
2
) to generate a bit that is to be transmitted. A second or third convolution code can be used to generate a second or third bit and thereby introduce redundancy as well as the information smearing in the transmitted symbols. These several bits are often combined and transmitted as a single symbol, represented perhaps by one state of a modulation constellation.
Referring to
FIG. 1
, an example of channel coding used for IS-95 is illustrated. The IS-95 encoder
10
has a series of delay line components
11
. A first set of selected signals from the terminals of the delay line components
11
are applied to a first XOR component
12
, while a second set of selected signals from the terminals of the delay line components are applied to a second XOR component
14
. This rate ½ code has constraint length 9, i.e. 9 delay line components
11
. Notice that for this encoder, each input bit results in two different output bits and that each of the two output bits depends on the current input bit and either four or five of the preceding eight input bits. Assuming that the preceding eight bits are fixed, there are only two output bit-pairs possible from XOR components
12
,
14
depending upon the next input bit. However, there are four possible output bit-pairs that could be transmitted in all when the preceding bits are not fixed.
Note that, for the exemplary IS-95 channel encoder, a single input bit affects the next 9 output bit pairs, no one of which reflects exactly the information of that single input bit. The convolution codes smear the information of the single input bit over eighteen bits of output bit pairs. The virtue of this smearing of information is that, when a single symbol (or even more than one symbol) is corrupted in transmission, the decoder often can still recover the input information bit.
Computing Metrics
Pairs of output bits become symbols that have some physical representation on the communications channel. These symbols are transmitted and the receiver makes a measurement of the resulting signal that it receives. Of course, the received signal differs from the signal that is transmitted and the difference between the two signals is called noise. The receiver can calculate the distance between the received signal and each of the four symbols that might have been transmitted. The details of the computation of this metric depend on the particular communications channel and how the states are represented physically.
In the receiver's computation of metrics, a first option provides for the conversion of the received signal to a digital signal (in this case a pair of bits) and then computation of the metric. Apparatus using this approach is called a hard decision decoder. The other option, which is more complex computationally but which generally results in fewer errors, is the computation of the metric from the original signal levels; this process being provided by a soft decision decoder.
Trellis Decoding
Referring next to
FIG. 2
, a four-state trellis diagram, according to the prior art, is illustrated. Each column of the trellis diagram represents a Viterbi decoder at an instant of time and the arrows in the diagram represent the transitions of that decoder from one instant of time to the next. Notice that the nodes of the diagram are labeled with a pair of binary digits, 00, 01, 10, 11, the binary digits representing the state numbers 0, 1, 2, and 3. Also observe that the arrows between nodes are labeled either 0 or 1 and that the label of each node is always formed by concatenating the labels any pair of arrows from two columns earlier that lead to that node. Expressed another way, the number of each node specifies the last two (because this is a four-state decoder) transitions made to get to that state. Of course multiple paths lead to each state, but these paths differ only at earlier transitions.
Referring once again to
FIG. 2
, in moving from one increment of time to the next, the Viterbi decoder, i.e., a decoder that decodes convolutionally encoded symbols, receives or computes metrics representing the distance from the received signal to what would be transmitted for an information bit of “0” and for an information bit of “1”. This computation is performed for each possible history of transmitted bits as encoded by the various state identification numbers. These metrics are referred to as transition metrics and they include the noise for a current symbol. The transition metrics are summed along the paths and these sums are called path metrics.
Two arrows represent transitions that can enter each node and two other arrows represent transitions that can leave each node. At each node, path metrics are associated with each incoming arrow. The trellis decoder selects the smaller path metric, i.e., the path metric representing the smaller noise figure of the two incoming signals. All of the paths associated with the non-selected arrow (i.e., transition) are permanently abandoned by the trellis decoder. The transition metric corresponding to an information bit of “1” is added to the surviving incoming path metric and the sum is forwarded to the node at the next time instant along the arrow labeled
1
. Similarly, the transition metric corresponding to an information bit of 0 is added to the surviving incoming path metric and sent to the node at the next time instant along the arrow labeled
0
. The configuration of two incoming arrows and the two outgoing arrows from a node can be described as a butterfly diagram.
Referring to
FIG. 3
, examples of butterfly diagrams are shown for a 16-state encoder. For each butterfly diagram, two states serve as input transitions to determine two states for the next time increment. For example, for the butterfly diagram represented by the solid lines, the states 0001 and 1001 serve as inputs to the determine the states 0100 and 0011 for the next time increment. Unfortunately, a significant amount of memory is needed to specify each state. In implementing the decoding algorithm, not only is the history information associated with each state retained, but the path metrics are also retained, i.e., for selecting between two input transitions that terminate on the same state. If the butterfly operations are processed as indicated in
FIG. 3
, two copies of these data groups would be required to be saved in order that the storage resulting from one butterfly diagram does not corrupt the input data needed to process the result of a different butterfly diagram.
An alternative to the doubling of the required memory is to re-assign the state table at each iteration as illustrated in FIG.
4
. Note also in
FIG. 4
, at each stage, the butterfly operation is applied in a quite regular fashion, the pattern merely changes from one time increment to the next time increment. Specifically, the height of the butterfly transition is c
De'cady Albert
NEC Electronics Inc.
Skjerven Morrill LLP
Torres Joseph D.
LandOfFree
Apparatus and method for implementing a decoder for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for implementing a decoder for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for implementing a decoder for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3001031