Pulse or digital communications – Multilevel
Reexamination Certificate
2000-03-23
2004-05-04
Ghayour, Mohammad H. (Department: 2631)
Pulse or digital communications
Multilevel
C375S264000, C375S265000, C375S340000, C375S342000, C375S287000, C714S792000, C714S794000
Reexamination Certificate
active
06731692
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to error correction coding, and more particularly, to a trellis encoder/decoder constellation mapping from binary data to symbols and inverse mapping suited to error-correction on a high-speed data channel.
2. Description of Related Art
To minimize the effects of additive white Gaussian noise (AWGN) as well as the effects of Rayleigh fading and other channel impairments, one or more error encoding techniques are used in order to provide for accurate transmission and detection of data, especially when very high level modulation schemes are employed.
Trellis-coded modulation is a forward error correction coding technique which is also well known in the art. Trellis codes are convolutional codes that are designed and optimized according to a specific modulation scheme. A convolutional encoder encodes information symbols based upon the present input symbol and the state of the encoder. The present state of the encoder is determined by the symbols which previously entered the encoder. That is, the encoded symbol is a function of the present input symbol and also symbols that entered the encoder before the present input symbol. Thus, a convolutional encoder has memory.
Convolutional codes are typically implemented by shift registers and summers. The next state and the output of the encoder are functions of the present state of the register or look-up table (i.e., the value of the bits presently stored within the register or look-up table memory), and the input to the register or look-up table.
FIG.
1
A and the accompanying table
230
shown in
FIG. 1B
illustrate an exemplary embodiment of a convolutional encoder
200
implemented by means of shift registers, and the corresponding state table. The encoder
200
is simply shown here in order to illustrate the operation and implementation of convolutional encoder, and is not to be construed as an implementation of the trellis encoder used in accordance with the present invention. The encoder
200
includes shift register memory units
205
,
210
,
215
, as well as summers
220
,
225
. A one-bit input is encoded into a two-bit output to provide rate ½ encoding.
Assuming an initial state of 000 (i.e., the register units
205
,
210
,
215
contain bit values of 0, 0, 0, respectively), and an input value of 0, the next state of the encoder
200
is 000 (a zero bit value shifts in while a zero value shifts out). Consequently, the value of the two bits at the output is 00. This is represented in the first line of the state table
230
if FIG.
1
B. Note, however, that the present and next state columns only indicate two-bit values since the last state bit is always shifted out and is not significant in determining the next state. Thus, when moving from state to state, the encoder
200
can be considered to have four possible present states and four next states, each two-bit values. As another example, assume the encoder
200
to be in the present state 10 (i.e., the first two registers contain 1,0). An input of 1 will move the encoder
200
to the next state of 11 (i.e., the first two registers contain 1,1) and generate an output of 01 (decimal 1). This process is repeated as each successive bit enters the encoder
200
so that a state diagram can be constructed which shows the possible state transitions of the encoder
200
with the accompanying input and output values which correspond to those transitions.
FIG. 2
is a state transition diagram which indicates the possible state transitions of the encoder
200
of
FIG. 1
, along with the input and output values corresponding to the possible transitions. Because the state transition diagram resembles a trellis in form, such diagrams are often called trellis diagrams, hence the name “trellis coding.” Each dot on the trellis diagram of
FIG. 2
represents a state of the encoder
200
. Dots in the same horizontal row correspond to the same state at different times. Dots in the same vertical column represent different states at the same time (i.e., within the duration of the same symbol). Branches between the dots represent possible state transition paths. Thus, for example, there is a branch between the state 01 and the state 00 which indicates that, given the appropriate input, the encoder
200
could go from state 01 to state 00. Since there is no branch between states 01 and 11, nor is there a branch between the states 01 and 11, it is possible for the encoder
200
to go from state 01 to either of the states 11 or 01 within one symbol duration.
The number pair along each of the branches depicted in
FIG. 2
indicate the [input, output] values which correspond to a given branch. The first number represents the input which causes the transition, while the second number represents the output value resultant upon this transition.
As seen from the trellis diagram of
FIG. 2
, the possible state transitions for the encoder
200
are the same for each successive symbol. Thus, the same pattern repeats over and over again for each symbol duration.
As an example, assume the encoder
200
begins in the state 0 (binary 00), represented by a dot
300
in FIG.
2
. Upon application of an input value 1 to the encoder
200
, the encoder
200
goes from state 0 to state 2 (binary 10), represented by a dot
320
, via a path
310
. Upon completion of the transition, the encoder
200
outputs a value 3 (binary 11). If the value of the next bit applied to the input is 0, the encoder
200
transitions from state 2 to state 1, represented by a dot
340
, via a path
330
, while the output of the encoder
200
assumes a value of 2. Finally, upon application of input bit of 0, the encoder
200
moves from the state 1 to the state 0, represented by a dot
360
, via a path
350
. Upon entering the 0, the encoder
200
outputs a value 3. Thus, in the foregoing example, input bits
1
-
0
-
1
are encoded by the encoder
200
into output bits
11
-
10
-
11
, or
3
-
2
-
3
in decimal. At the same time, the encoder
200
has transitioned from the state 0 to the state 2, to the state 1, and back to the state 0.
As further explained below, convolutional encoding (and Viterbi decoding) provides for a reduced number of detected errors at the receiver. Consider again the trellis diagram of FIG.
2
. For example, assume that a three-bit data stream
1
-
0
-
0
is properly encoded as
11
-
10
-
11
by the encoder
200
as described above. Also suppose that the receiver detects the transmitted signal erroneously as
11
-
11
-
11
. In order to determine what the original transmitted data is, the decoder performs a maximum likelihood decision based upon the possible state transition paths which the encoder
200
might have taken. Since the encoder is typically set to state 0 at initialization, the decoder assumes that the detected sequence of data bits began in state 0. The decoder then examines all of the paths which began at state 0 and terminate at a state three symbols later as depicted in
FIG. 2
for the purpose of illustration. For instance, for an ending point at the state 0, at the point
360
, there are two possible paths which the encoder may have taken: the path
310
,
330
,
350
, or the paths
370
,
380
,
390
. Of course, all the other paths of three symbol duration are also examined to determine the likelihood that the detected bit sequence followed these possible paths, but for the sake of simplicity of illustration, only the paths from state 0 to state 0 are considered here.
In order to identify the most likely path, the decoder determines the probability that the detected data sequence was produced by the first path (e.g., the path
310
,
330
,
350
), the probability that the detected data sequence was generated by the second path (e.g., the path
370
,
380
,
390
), and so on until a probability has been calculated for each possible path. The path having the highest probability is then selected as the actual path according to either hard or soft decision methods described in greater detail below
Agere Systems Inc.
Ghayour Mohammad H.
Ghulamali Qutub
LandOfFree
Symbol encoding and decoding architecture for trellis-coded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Symbol encoding and decoding architecture for trellis-coded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbol encoding and decoding architecture for trellis-coded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3200048