Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1999-11-22
2004-01-20
Tran, Khai (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S265000, C714S795000
Reexamination Certificate
active
06680986
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to method for implementing a single chip shared channel decoder supporting a multiplicity of variable bit rate carriers. More particularly, the present invention relates to a method for decoding an input signal comprising a plurality of channel symbols utilizing Viterbi decoding for use in onboard processing satellites in which trade-offs are made between memory for storing the survivor paths and bit error rate performance.
BACKGROUND OF THE INVENTION
Among several conventional algorithms for decoding convolutional codes, the Viterbi algorithm achieves maximum likelihood decoding and has been extensively utilized to improve the reliability of digital communication links. For each received channel symbol in an encoded input signal, the Viterbi algorithm initially computes a set of branch metrics. The branch metrics are then used by add/compare/select (ACS) units for computing and updating path metrics. For each state, in addition to the new path metrics, a sequence of decisions are made for the survivor paths and stored. When memory space is readily available and delay is not of any concern, the decoder can continue processing received data and output estimates for information bits at the end of message. In practice, however, messages are truncated and after a delay of T decoding steps, the decoder outputs estimates for information bits in a continuous mode.
There are two approaches to implement the truncated Viterbi algorithm. In a first approach, known as survivor exchange, the path metrics, as well as the survivor paths, are updated by the ACS operation and routed among the neighboring trellis states. As shown in
FIG. 1
, the subsystems of the truncated Viterbi algorithm decoder using the survivor exchange method comprise a branch metric calculator
11
for computing branch metrics B
t
, a plurality of add-compare-select (ACS) units
12
for computing path metrics &Ggr;
t
and survivor paths E
t
, a memory
13
for storing new path metrics &Ggr;
t
and the survivor paths E
t
, and a memory
14
for storing path metrics &Ggr;
t−1
and survived paths E
t−1
, of prior trellis/decoding step t−1. For a code of rate ½ or its punctured versions, the truncation length T is about 60 to 120 bits. While this approach may provide savings in the required memory for storing survivor paths it entails a large interprocessor communication bandwidth and a large percentage of the chip area must be allocated to wiring.
In a second approach known as a traceback method, the sequence of survived paths are stored in a traceback RAM which is placed outside of the ACS units. As shown in
FIG. 2
, the subsystems of the truncated Viterbi algorithm decoder using the traceback method comprise a branch metric calculator
11
for computing branch metrics B
t
, a plurality of ACS units
12
, and a memory
23
for storing new path metrics &Ggr;
t
, a memory
24
for storing old path metrics &Ggr;
t−1
. Communications between each of the ACS units
12
and a traceback module (not shown) can be as small as one bit per decoder state per decoding step. Number of cells in the traceback RAM is a linear function of the product of number of decoder states S which equals 2
m
, where m is the memory order of the code, and the truncation length T.
Studies on the feasibility of VLSI implementation of a shared channel decoder (SCD) using the Viterbi algorithm have indicated that the maximum number of carriers processed by a single chip decoder is limited by the chip space allocated for storing the survived paths. This conclusion is valid for both the traceback method and the survivor exchange method for implementing a Viterbi algorithm decoder. The importance of RAM for storing surviving paths is emphasized by noting that it occupies about 50 percent of the chip area of a single channel decoder.
SUMMARY OF THE INVENTION
A decoding method and apparatus is presented which provides a high degree of flexibility allowing tradeoffs among such important system parameters as processing speed, required on-chip RAM, bit error rate (BER) performance, and throughput. The decoding method of the present invention uses the Viterbi algorithm for selecting survivor paths terminating on each trellis state. This decoding method is then applied for realization of a SCD. Several variations of the decoding method are examined for minimizing the required chip space of an Application Specific Integrated Circuit (ASIC) and optimizing the maximum number of channels. In a maximum likelihood shared channel decoding procedure, the ACS units must operate at 16×64 Kbps, or 1 Mbps for decoding a group of sixteen 64 Kbps channels. However, with the current CMOS technology, the same ACS units, occupying roughly the same amount of chip area, can operate more than 60 MHz. The decoding of the present invention method takes advantage of the high speed capability of processing elements for reducing the amount of memory required to store the survived paths.
For the special frequency plan and configuration of shared demodulators, considered for the onboard processing satellites, it is assumed that each channel is either a 64 Kbps carrier, or a 2 Mbps carrier, encoded by a convolutional code of rate ½ or its punctured version. In the midband section, it is assumed that frequency is planned so that each demodulator either demodulates only one 2 Mbps carrier or up to sixteen 64 Kbps carriers. The BER performance of the proposed decoding algorithm is evaluated by computer simulations. Feasibility of a single chips SCD for simultaneously decoding up to sixteen 64 Kbps channels is examined for the midband. For the sidebands, a SCD using MLD is proposed since there are at most six 2 Mbps carriers in these bands.
The required chip space can be minimized by selecting an architecture which is based on parallel processing of states and bit serial communications among the neighboring states. While the decoding method of the present invention is intended for an onboard processing satellite, it can certainly be also used in satellite or terrestrial earth stations receiving several low bit rate channels.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features, aspects and advantages of the present invention will become better understood with reference to the following detailed description, appended claims, and accompanying drawings, wherein:
FIG. 1
is a block diagram of a truncated Viterbi Algorithm decoder using the survivor exchange method;
FIG. 2
is a block diagram of a truncated Viterbi Algorithm decoder using a traceback module;
FIG. 3
is a block diagram of a truncated Viterbi Algorithm decoder according to a first embodiment of the present invention;
FIG. 4
is a flowchart of the method of implementing a truncated Viterbi Algorithm decoder according to a first embodiment of the present invention;
FIG. 5
is a block diagram of a truncated Viterbi Algorithm decoder according to a second embodiment of the present invention;
FIG. 6
is a flowchart of the method of implementing a truncated Viterbi Algorithm decoder according to a second embodiment of the present invention;
FIG. 7
is a graph illustrating the number of gates vs. truncation length for the decoding method of the first embodiment of the present invention;
FIG. 8
is a graph illustrating the number of gates vs. truncation length for the decoding method of the second embodiment of the present invention;
FIGS. 9-13
are graphs illustrating BER performance for different truncation lengths for the decoding method of the first embodiment of the present invention;
FIGS. 14-18
are graphs illustrating BER performance for different truncation lengths for the decoding method of the second embodiment of the present invention;
FIG. 19
illustrates a configuration for memory for storing branch metrics;
FIG. 20
illustrates a configuration of ACS units.
REFERENCES:
patent: 5970104 (1999-10-01), Zhong et al.
patent: 6415415 (2002-07-01), Karabed
patent: 6452984 (2002-09-01), Banister et al.
Oliver M. Collins, Member; The
Intelsat Global Service Corporation
Tran Khai
LandOfFree
Method for implementing shared channel decoder for onboard... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for implementing shared channel decoder for onboard..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for implementing shared channel decoder for onboard... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260466