Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-14
2004-07-27
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S795000
Reexamination Certificate
active
06769090
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to channel coding and decoding in digital communications, particularly high-speed, broadband wireline communications.
2. State of the Art
Channel coding refers to data transformations, performed after source encoding but prior to modulation, that transform source bits into channel bits. Trellis coding is one class of channel coding. Trellis encoders and decoders find widespread use in digital communications, an example of such use being xDSL modems such as HDSL2/G.SHDSL modems. One specific trellis decoder is the Viterbi decoder. Trellis encoders and Viterbi decoders are described, for example, in U.S. Pat. No. 5,457,705, incorporated herein by reference.
A block diagram of a known data transmission system using a trellis encoder and a Viterbi decoder is shown in FIG.
1
and includes a transmitter comprising convolutional encoder
41
, mapping circuit
42
for setting an arrangement of signal points, and 8-PSK (phase shift keying) modulator
43
for phase-modulating which is supplied with 8 signal points generated by 2
3
bits, and a receiver comprising 8-PSK demodulator
44
and Viterbi decoder
45
. Convolutional encoder
41
produces output signal points Y
2
, Y
1
, Y
0
that are mapped into the position shown in
FIG. 2
of the accompanying drawings by mapping circuit
42
and then modulated by 8-PSK modulator
43
for transmission to a transmission path. The 8-phase-modulated signal, with noise added during transmission, is demodulated into m-bit soft decision I channel, Q channel (I-ch., Q-ch.) data by 8-PSK demodulator
44
. The m-bit soft decision I-ch., Q-ch. data are supplied to Viterbi decoder
45
, which produces estimated information data d. Although different data transmission systems use different modulation coding arrangements, some of which may only be one-dimensional instead of two-dimensional (I, Q), the foregoing system may be regarded as exemplary for purposes of the present discussion.
A block diagram of a typical trellis encoder, or convolutional encoder, is shown in
FIG. 3
, operation of which will be described. Convolutional encoder
41
is supplied with parallel information bits X
1
, X
2
that have been converted by serial/parallel converter
101
connected to input terminals
77
,
78
of convolutional encoder
41
. If the encoding ratio is 2/3, then exclusive-OR gates
85
,
86
of convolutional encoder
41
output exclusive-OR of information bits X
1
, X
2
supplied from input terminals
77
,
78
and output signals from shift registers
82
,
83
, and are stored in respective shift registers
83
,
84
. At this point, convolutional encoder
41
outputs, as encoded data, output signals Y
1
, Y
2
as respective information bits X
1
, X
2
and redundancy bit Y
0
from respective output terminals
80
,
79
,
81
. Each time information bits X
1
, X
2
are inputted, convolutional encoder
41
repeats the above operation and produces output data Y
1
, Y
2
, Y
0
. Output data Y
1
, Y
2
, Y
0
are then mapped into the positions shown in
FIG. 2
by mapping circuit
42
of FIG.
1
. If there are three input information bits X
1
, X
2
, X
3
and the encoding ratio is 3/4, then, assuming that convolutional encoder
41
is used, convolutional encoder
41
adds redundancy bit Y
0
depending on information bits X
1
, X
2
to information bits X
1
, X
2
, X
3
, and produces 4-bit output data.
Operation of Viterbi decoder
45
will be described below with reference to
FIG. 4
,
FIG. 5
,
FIG. 6
, and
FIG. 7
of the accompanying drawings.
FIG. 4
shows the trellis transition of convolutional encoder
41
.
FIG. 5
shows an ACS (add compare select) circuit composed of adders
50
through
53
, comparator
54
, and selector
55
, and
FIG. 6
also shows the ACS circuit.
FIG. 7
shows Viterbi decoder
45
. In
FIG. 7
, the m-bit soft decision I ch., Q ch. data decoded from an 8-PSK signal are supplied from input terminals
87
,
88
, respectively, to branch metric generator
89
, which determines likelihood estimates (branch metrics) BM
0
, BM
1
, . . . , BM
7
between the 8-phase signal points and reception points as shown in FIG.
2
. The likelihood estimates BM
0
, BM
1
, . . . , BM
7
are supplied to ACS circuit
90
. To process a 0th state as shown in
FIG. 5
, branch and path metrics BM
0
′, PM
0
, branch and path metrics BM
2
′, PM
2
, branch and path metrics BM
4
′, PM
4
, and branch and path metrics BM
6
′, PM
6
are added by respective adders
50
,
51
,
52
,
53
, and a path metric with maximum likelihood is calculated by comparator
54
and selected by selector
55
as a path metric PM
0
on the next occasion. It is assumed that a path that has transited from a 4th state is selected. Upon selection of the path, the history data of the path stored in 4th-state shift register
75
(see
FIG. 6
) in path memory
91
is shifted to the right into 0th-state shift registers
73
by select signals SEL
0
applied to selectors
56
,
60
,
64
,
68
, so that 0th-state shift registers
73
store two information bits “01” that are a transition output. Similarly, the above operation is simultaneously carried out with respect to the 1st, 2nd, . . . , 7th states by circuits based on the trellis transition shown in FIG.
4
. Each time a received symbol is inputted, path metrics PM
0
-PM
7
with maximum likelihood are detected by maximum likelihood decider
92
, and the output signal from the final shift register which represents the state of the most likelihood path is selected by selector
72
, thus producing estimates X
2
, X
1
indicative of estimated decoded bits.
In order to cover a wide variety of services XDSL standards, such as G.SHDSL, typically specify more than one data rate. Moreover, past experience dictates the need for higher and higher data rates. There are various ways to address this issue of high data rate system with multi-rate functionality. One straightforward approach is to increase the bandwidth of the transmitted signal in proportion to the required data rate. However, this is not a very efficient use of the bandwidth. Another approach is to change the number of bits per symbols, i.e., more bits per symbols for higher data rates. In this approach it is not necessary to increase the bandwidth.
The difficulty of the variable bits per symbol is that if proper care is not taken, the associated trellis encoding/decoding arrangement can become unduly complex. What is needed is a careful design of the trellis encoding/decoding arrangement so that the multiple bits per symbol for various data rates can be used seamlessly. The present invention addresses this need.
SUMMARY OF THE INVENTION
The present invention, generally speaking, provides efficient trellis encoder/decoder structure that is suitable for accommodating multiple bits per transmitted symbol. On the encoder side for every rate we map the input bits to a transmitted symbol in such a way that the logic required for decoding the encoded bits is virtually the same irrespective of the number of bits per symbol. This results in greatly simplified decoder structure.
REFERENCES:
patent: 4493082 (1985-01-01), Cumberton et al.
patent: 4606027 (1986-08-01), Otani
patent: 5220570 (1993-06-01), Lou et al.
patent: 5457705 (1995-10-01), Todoroki
patent: 5502736 (1996-03-01), Todoroki
patent: 5509021 (1996-04-01), Todoroki
patent: 5651032 (1997-07-01), Okita
patent: 5737365 (1998-04-01), Gilbert et al.
patent: 5751734 (1998-05-01), Choi et al.
patent: 5796756 (1998-08-01), Choi et al.
patent: 5838729 (1998-11-01), Hu et al.
patent: 5928378 (1999-07-01), Choi
patent: 5946361 (1999-08-01), Araki et al.
patent: 5970104 (1999-10-01), Zhong et al.
patent: 5995562 (1999-11-01), Koizumi
patent: 6233712 (2001-05-01), Rhee et al.
patent: 6269129 (2001-07-01), Rhee et al.
patent: 6353640 (2002-03-01), Hessel et al.
patent: 6370202 (2002-04-01), Wolcott
Falconer, David D. and Ljung, Lennart, “Application of Fast Kalman Estimation to Adaptive Equalization,” IEEE Trans. on Comm., COM-26, No. 10 (Oct. 1978
Baker Stephen M.
Burns Doane , Swecker, Mathis LLP
Virata Corporation
LandOfFree
Unified technique for multi-rate trellis coding and decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Unified technique for multi-rate trellis coding and decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unified technique for multi-rate trellis coding and decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3226183