Pulse or digital communications – Bandwidth reduction or expansion – Pulse code modulation
Reexamination Certificate
2000-03-24
2003-01-14
Pham, Chi (Department: 2631)
Pulse or digital communications
Bandwidth reduction or expansion
Pulse code modulation
Reexamination Certificate
active
06507619
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital communication systems. More particularly, the invention relates to decision decoding of received digital information for use in subsequent decoding processes.
2. Background of the Related Art
The process of transmitting digital information may in one sense be thought of as a four-step process as shown in FIG.
1
. First, an incoming data stream of electrical digital signals x(t) is coded by a coder
10
to produce coded information C(x(t)) that is provided to a transmitter
20
which transmits the coded information C(x(t)) over a communication medium
30
. The coder
10
processes the data stream x(t) so that the coded information C(x(t)) is robust to errors; that is, errors in the coded information C(x(t)) can be detected and corrected. This is necessary because, as will be seen, the transmission process introduces a noise component into the transmitted signal which would corrupt the signal and render it useless were it impossible to be removed.
In an exemplary case, the incoming data x(t) is digitized audio such as voice or music from a known source; the coding unit
10
applies a coding transformation to the incoming data x(t) to produce the coded information C(x(t)); and the transmitter
20
modulates a radio-frequency signal with the coded data C(x(t)) to send it as a radio-frequency signal through the atmosphere which serves as the communication medium
30
.
In traversing the communication medium
30
, the transmitted information C(x(t)) acquires a noise component n(t), and the resultant signal x′(t)=C(x(t))+n(t) received by a receiver
40
is decoded by a decoding unit
50
to recover the original data stream.
In the above example, the receiver
40
demodulates the received radio frequency signal to produce the received coded information C(x(t))+n(t). The received coded information is error-checked and decoded by the decoding unit
50
to produce the outgoing digital data stream which might then be converted to an analog signal to be amplified for driving a speaker.
It is common in systems such as the one described above for the coder
10
to code C(x(t)) using a convolutional coding system. In contrast to a block code where a block of bits is coded according to a rule defined by the code without regard to previous inputs to the coder, a convolutional code additionally makes use of previous bits it processed in the coding process; thus, the coder
10
is a type of finite state machine.
An example of a convolutional coder of a type which might be used in the coder
10
is shown in FIG.
2
A. As is evident from the coder block diagram, coding in this unit depends not only on the state of the current input bit x
n
but also on the state of the two previous input bits held in the two latches D. Consequently, the coder is a four-state machine as shown by its state diagram in FIG.
2
B. From the state diagram it is relatively straightforward to derive the coder's trellis diagram as shown in FIG.
2
C. Here, the branch to a particular state corresponding to a zero input is represented by a solid arrow, and the branch a particular state corresponding to a one input is represented by a dotted arrow.
With the trellis diagram of
FIG. 2C
, the coding process will be readily apparent to those skilled in the art. Applying an input vector of, e.g., X=(1 1 0 1 0 1 1) produces outputs from the coder of
FIG. 2A
as shown in TABLE I (assuming the coder starts from an all-zero state).
TABLE I
Input x
1
Internal State D
1
D
2
Output Y
1
Y
2
1
0
0
1
1
1
1
0
0
1
0
1
1
0
1
1
0
1
0
0
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
Thus, for the coder of
FIG. 2A
, C(X)=(1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1).
If the communication medium
30
were error-free and the receiver
40
were assured of providing C(X) to the decoder
50
, it could recover the original data stream simply by applying C(X) to the trellis network of the coder state machine and track the path therethrough which generated the sequence C(X). For example, C(X)=(1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1) wound be generated by the path shown in
FIG. 3
, where states occupied by the coder are shaded and branches taken by the coder are in bold, with the corresponding coder output C(X) given above each stage. From this, the original input sequence X=(1 1 0 1 0 1 1) can be obtained.
The above discussion and those hereinafter assume that the coder
10
and decoder
50
operate according to the same coding algorithm; that is, they both base their processing on the same coder circuit, state machine and the like; thus, dimensions of the trellis network necessary to accurately represent the coding algorithm are known to the decoder, the number of stages necessary in the trellis network is known, etc. Further, for the purposes of explanation only it is assumed that in this example the coder state machine begins in an all-zero state (this is not a requirement of real-world systems), and that the input stream X is padded with a sufficient number of zeroes to return it to such a state at the conclusion of the coding/decoding process.
Assume now that the signal received and processed by the receiver
40
has a non-zero noise component. This might result in the decoding unit
50
receiving C′(X)=(1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1), with the sixth and eleventh bits being errors due to n(t). In this case, the original input sequence cannot be found simply by applying C′(X) to the trellis of
FIG. 2C. A
typical error-correction algorithm used in this situation is the Viterbi error correction algorithm described as follows.
1. Given the trellis network, associate a metric with each stage in the trellis and set the metrics for all states in the first stage to zero.
2. For each state in the next stage, find the “distance” of each branch to it from the next-received subsequence of C′(X) and add it to the metric of the current state from which it branches.
3. Choose the minimum of the values calculated in Step
2
as the metric for the given stage in the next stage, and choose the branch leading to it as the survivor branch to that state.
4. Repeat Steps
2
and
3
until the end of the trellis network is reached.
5. Select the state in the last stage of the trellis network having the minimum metric and work backwards to the beginning by selecting survivor paths to produce the best guess about C(X).
If the coder is known to start from an all-zero state, the system is preferably designed so that traceback is always done to the all-zero state in the first stage. This can be done by, for example, initializing the all-zero state to zero and initializing the other states to large values.
Also, there are various techniques available to determine the state from which to begin a traceback. For example, at the end of a frame when the coder ends in a known state (in the example, 00), start the traceback from that known state.
Application of the Viterbi decoding algorithm to the corrupted stream C′(X) and the trellis network of
FIG. 2C
is shown in FIG.
4
. Here,
the metric for a state is shown at its center;
the distance of a current subsequence from a given branch is shown by a number above the branch;
survivor branches (except for those in the best guess path) have a white arrowhead; and
the best guess path is in bold.
First, metrics of all states in the initial stage are set to zero. Then, the distance (here, the Hamming distance) between the subsequence 11 and each branch value is assigned to that branch. For the first node, the two branches are 00 and 11, so they receive values of 2 and 0. The next node has branches 01 and 10, so each of these branches receives a metric of 1. The third node has branches 11 and 00, so they respectively receive values of 0 and 2. Finally, the fourth node has branches 10 and 01 which each receive a Hamming distance of 1.
Then, for the first state in the second stage, the two branch values to it are 2 and 0, so its metric is set at 0 and the 0
Husted Paul J.
Thomson John S.
Atheros Communications Inc.
Bayard Emmanuel
Pham Chi
Pillsbury & Winthrop LLP
LandOfFree
Decoding system and method for digital communications does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding system and method for digital communications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding system and method for digital communications will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000794