Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-08-19
2002-04-16
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S795000, C714S796000
Reexamination Certificate
active
06374387
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to channel decoders for digital wireless communications devices. More particularly, the present invention provides a method and apparatus for a digital wireless communications device to decode in real-time a received signal which was encoded using a punctured convolutional code. In a preferred embodiment, a channel decoder is provided which permits Viterbi decoding of signals which have been encoded with a convolutional code, including a punctured convolutional code, without determining the branching metric in real-time.
2. Discussion of Related Art
FIG. 1
is a simplified block diagram of a reception portion of a digital wireless communications device
100
, such as a digital cellular phone which may be used with a TMS320C5x digital signal processor made by Texas Instruments, Dallas Tex. or other suitable processor. A preferred digital cellular phone may include an antenna
102
, a duplexer
104
, a mixer
106
, an oscillator
108
, a demodulator
110
, a 90°-phase shifter
112
, an equalizer
114
, a channel decoder
116
, a speech decoder
118
, a digital-to-analog converter (DAC)
120
, and a speaker
122
.
The reception portion of the digital cellular telephone of
FIG. 1
may operate in the following manner. A digital communications signal may be received by the antenna
102
and passed through the duplexer
104
to the reception portion of the digital communications device
100
. The mixer
106
steps the received signal to a lower workable frequency (called an intermediate frequency) by mixing the received signal with a frequency provided by an oscillator
108
. The signal, now at an intermediate frequency, is demodulated by the demodulator
110
. The demodulator
110
extracts information from the intermediate frequency. The demodulator may receive a signal from the oscillator
108
which has been shifted 90° by the 90°-phase shifter
112
. A preferred modulation (and thus demodulation) technique is differential quaternary phase-shift keying (DQPSK), but other modulation techniques may also be used.
The demodulated signal is then sent to the equalizer
114
to be equalized to account for channel distortion such as Rayleigh fading (caused by multi-path effects) and Doppler effects (caused by the movement of the transmitter with respect to the received signal). The equalizer
114
is essentially an inverse filter of channel distortion. The channel decoder
116
detects and corrects errors in the bit stream, demultiplexes control data, and feeds the data to the speech decoder
118
. As discussed below, if a convolutional encoding scheme, such as a punctured convolutional encoding scheme, was used to encode the received signal, a Viterbi decoding scheme may be used to detect and correct errors in the bit stream. The channel decoded signal is then sent to the speech decoder
118
, which decodes any speech encoding which may have been performed on the received signal. A preferred speech coding method is vector sum excited linear prediction (VSELP), but other speech coding methods may also be used. The DAC
120
converts the digital signal into an analog signal suitable to drive the speaker
122
.
One method to improve the reliability of a telecommunications network is to add error control processing at the transmitting and receiving ends of the network. One method of doing this is to add redundancy to the transmitted signal so that the receiving channel decoder
116
may make a decoding decision based on more than a single bit.
One common type of error control technique used in digital telecommunications networks is a convolutional code. A convolutional code is a code which provides n output symbols for each group of k input symbols. The code rate is defined as R=k
. For example, if two symbols are output for every one input symbol, the code rate is 1/2. While convolutional encoding provides adequate redundancy for effective error control, it also increases the bandwidth of the signal because it adds a number of symbols to the transmitted signal. The inverse of the code rate is known as the bandwidth expansion of the unpunctured convolutional encoder. Thus, for a 1/2 code rate, the bandwidth expansion is 2, i.e., the bandwidth used by signal is doubled.
One way to improve the bandwidth expansion of convolutional codes is to “puncture” the code. Puncturing a convolutional code means that periodically a certain number of bits in the convolutional encoder output are deleted at a fixed rate. This rate is called the puncture rate.
FIG. 2
illustrates an example of a convolutional encoder
200
. In this exemplary encoder
200
, two bits Y
1
and Y
2
are provided to the convolutional encoder and the encoder outputs a bit Y
0
. The Y
0
bit carries only forward error correction information and thus is referred to as a redundant bit. As seen in
FIG. 2
, a typical convolutional encoder is a 3-bit shift register having three states
202
,
204
,
206
interconnected by AND and XOR logic (not shown). The combined set of three bits
202
,
204
,
206
of encoder memory (S
0
, S
1
, S
2
) is typically referred to as the delay state. The output bits (Y
0
, Y
1
, Y
2
) are grouped into an output symbol typically referred to as the path state. Note that given a particular delay state (S
0
, S
1
, S
2
) not all path states may be possible in that time interval.
Because the encoder
200
may be considered to be a finite state machine, a finite state diagram may be used to represent the possible states the machine may be in at a particular time.
FIG. 3
is a trellis diagram
300
of an encoder which may be in one of either of two states: 0 or 1. This trellis diagram
300
is often referred to as a Viterbi butterfly. As seen in
FIG. 2
, the encoder
200
has m delay elements (in this example, m=3) and may be described as having 2
m
(in this example, 8) states, a.k.a. trellis states. For each new information bit shifted into the register, r output bits (in this example, 3) are generated by the multiplexing of r different generator polynomials g, where g is a generator polynomial described by a set of XOR operations on selected delay elements of the encoder
200
. For each steady state of the register, these output bits (or one output symbol) are used to describe the state transition from the previous steady state of the register to the current steady state of the register. This output symbol shall hereinafter be referred to as a “transition symbol”. There are 2
r
(in this example, 8) possible different transition symbols.
For each current state, there are two possible new states. These states are determined by whether the new information bit is a 0 or 1. Likewise, for each current state there are two possible previous states (0 or 1). This is illustrated in
FIG. 3
, which is a trellis structure
300
illustrating the possible states of the convolutional encoder
200
of FIG.
2
. In
FIG. 3
, the designation 0/xyz indicates a 0 input bit and a transition symbol of xyz; the designation 0/xyz indicates a 0 input bit and that the transition symbol is the complement of xzy (in the text, italicized type indicates “complement”.) The function of a decoder is to determine the most likely output. One way to do this is to use a sequence of states to determine the path having the lowest “cost”, i.e., the path which deviates the least from the received signal. Cost functions may be unique to each modulation technique. One commonly used cost function is a Hamming distance, which is often used for binary signals. (Although Hamming distances are described and claimed herein, a person skilled in the art readily recognizes that other suitable cost functions may be used.) A Viterbi decoder, for example, determines the most likely sequence of states experienced by the convolutional encoder
200
when it encodes the received signal.
A Hamming distance d
h
may be determined by accumulating the result of an exclusive-or (XOR) operation between each bit of the received code and the respective bits of the trellis
Baker Stephen M.
Institute of Microelectronics
Proskauer Rose LLP
LandOfFree
Viterbi decoding of punctured convolutional codes without... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Viterbi decoding of punctured convolutional codes without..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding of punctured convolutional codes without... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2890597