Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-12-23
2004-02-10
Chin, Stephen (Department: 2634)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S340000, C714S786000, C714S795000
Reexamination Certificate
active
06690750
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to Viterbi decoding systems, and in particular to a system and method for providing flexible, high-speed, and low-power decoding (based on the Viterbi algorithm) of convolutional codes for wireless and other type communication applications.
BACKGROUND OF THE INVENTION
Modern society has witnessed a dramatic increase in wireless communications. Wireless technology (e.g., satellite, microwave) has provided a system whereby cellular and other communications have become an ever increasing necessity. In order to satisfy the demand for increased and reliable communications capability, more flexible, powerful, and efficient systems are needed. In particular, forward error correction systems must be improved to satisfy society's need for increased wireless communications.
Forward error correction systems are a necessary component in many of today's communications systems. These systems generally add robustness to communications systems by substantially correcting errors that may occur during transmission and reception of wireless data. This is particularly true for systems which are limited in power and/or bandwidth. Often, convolutional coding is a key part in such forward error correction systems. In general, convolutional coding systems introduce redundancy data into a wireless data transmission so that random errors occurring in the transmission have a high probability of being corrected. Consequently, decoding systems (e.g., a Viterbi decoder) must be in place to decode the convolutionally coded data upon reception of the transmitted data, and thereby reconstruct the actual data transmission.
Referring to prior art
FIG. 1
, a wireless communications system
10
illustrates a particular challenge presented to a conventional wireless system. A transmitter
20
directs a communications signal
24
to a satellite system
30
. The satellite system
30
, upon receiving the communications signal
24
, then directs a communications signal
24
a
to a ground base station
32
wherein the signal is processed for the intended destination. Anytime during transmission of the communications signal
24
and
24
a
, noise
34
may corrupt a portion of the transmission (cause an error), thereby causing improper signal reception at the base station
32
. If error correction systems were not provided, the signal would likely have to be re-transmitted in order to be properly received at the base station
32
. Thus, inefficiencies and increased costs are likely results.
FIG. 2
illustrates a prior art error correction system
40
employing convolutional encoding and Viterbi decoding for increasing the likelihood that transmission signals may be properly communicated despite the presence of noise. Input data
42
(e.g., audio, video, computer data) is input to a convolutional encoder
44
. Encoded data is provided as a sequence of data bits
46
(also referred to as encoded symbols), which are composed of actual and redundantly added data, and transmitted over a communications link
48
. The communications link
48
may introduce noise into the data transmission and therefore, the transmitted data bits
46
may be corrupted by the time they reach their destination. Each received (and possibly corrupted) data bit
46
a
may be processed by a Viterbi decoder
50
to provide decoded output data
52
. The Viterbi decoder
50
, (based upon the Viterbi algorithm which was first proposed by Andrew Viterbi in 1967), provides a decoding system wherein the input data
42
that was originally transmitted may be determined to a high probability even though noise may have affected some of the transmitted (convoluted) data
46
. In general, the input data
42
may be determined by computing a most likely sequence for the input data
42
which is derived from the convolutionally encoded data
46
a.
Convolutional encoding is performed by convolving (redundantly adding) input data bits
42
via an encoder with one or more previous input bits
42
. An example of a conventional rate ½, constraint length
9
, convolutional encoder
44
is shown in prior art FIG.
3
. Input bits
42
are input to a series of delay elements
60
, such as a shift register
44
a
, that provides outputs X
0
through X
8
at various points. The outputs X
0
through X
8
may be combined by an XOR function
62
a
and
62
b
to generate an encoded symbol set G
0
and G
1
. The outputs, X
0
through X
8
, which are connected (tapped) to the XOR function
62
a
and
62
b
, will determine an output code sequence of G
0
and G
1
for a given input data sequence
42
. The input to output relationship may be described by a code polynomial for the encoder outputs G
0
and G
1
. For example, for the encoder
44
shown in
FIG. 3
, the code polynomial is given as:
G
0
=X
0
+X
1
+X
3
+X
6
+X
8
=1
+X
1
+X
3
+X
6
+X
8
; and
G
1
=X
0
+X
2
+X
3
+X
7
+X
8
=1
+X
2
+X
3
+X
7
+X
8
Note: Texas Instruments Applications Report SPRA071, Viterbi Decoding Techniques in the TMS 320C54x Family, 1996, provides further details on convolutional encoders and code polynomials and is hereby incorporated by reference in its entirety.
As shown, the encoder
44
of
FIG. 3
, generates the encoded symbol set, G
0
and G
1
, for every input bit
42
. Thus, the encoder has a rate of ½ (
1
input/
2
output). The constraint length (K) represents the total span of combinations employed by the encoder which is a function of the number of delay elements
60
. A constraint length K=9 implies there are 2
(9−1)
=256 encoder states (the ninth bit is the input bit). These states are represented as state S
0
(binary 00000000) to state S
255
(binary 11111111).
Convolutionally encoded data may be decoded according to the Viterbi algorithm. The basis of the Viterbi algorithm is to decode convolutionally encoded data by employing knowledge (e.g., mimic the encoder) of the possible encoder
44
output state transitions from one given state to the next based on the dependance of a given data state on past input data
42
. The allowable state transitions are typically represented by a trellis diagram (similar to a conventional state diagram) which provides possible state paths for a received data sequence based upon the encoding process of the input data
42
. The trellis structure is determined by the overall structure and code polynomial configuration of the convolutional encoder
44
described above. The Viterbi algorithm provides a method for minimizing the number of state paths through the trellis by limiting the paths to those with the highest probability of matching the transmitted encoder
44
output sequence with the received data sequence at the decoder.
FIG. 4
is an illustration of a portion of a trellis
66
and depicts a basic Viterbi algorithm butterfly computation. Four possible encoder transitions
70
a
through
70
d
from present state nodes
68
a
and
68
b
, to next state nodes
68
c
and
68
d
are illustrated. As shown, two transition paths (branches) exist from each present state node
68
a
and
68
b
to each next state node
68
c
and
68
d
. The Viterbi algorithm provides a process by which the most likely of two possible transition paths may be determined and subsequently selected as a portion of a “survivor” path. For example, branches
70
a
and
70
b
provide two possible transition paths to the next state node
68
c
. Likewise, branches
70
c
and
70
d
provide two possible transition paths to the next state node
68
d
. The transition paths
70
a
through
70
d
provide the possible directions to the next most likely states that may be generated by the convolutional encoder
44
as directed by the input bits
42
. Once a sequence of survivor paths have been determined (through a plurality of butterfly stages), the most probable data input sequence
42
to the convolutional encoder
44
can be reconstructed, thus decoding the convolutionally encoded da
Gatherer Alan
Hocevar Dale E.
Brady III W. James
Chang Edith
Chin Stephen
LandOfFree
Flexible Viterbi decoder for wireless applications does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexible Viterbi decoder for wireless applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible Viterbi decoder for wireless applications will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3309538