Excavating
Reexamination Certificate
1997-07-16
2001-07-10
Elmore, Reba I. (Department: 2786)
Excavating
37, 37, 37, 37, 37, 37, C375S213000, C375S260000, C375S285000, C375S341000, C341S107000
Reexamination Certificate
active
06257756
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to digital communications, and more particularly, to error correction techniques using the Viterbi algorithm.
BACKGROUND OF THE INVENTION
A primary goal in digital communications is the transmission of data in error-free form. During transmission, the data is subjected to noise which may cause errors in the received data. To improve the reliability of data transmission, one of a variety of possible error correction techniques is commonly used. For example, a known error correction technique is convolutional coding. This technique provides an effective error correction capability but requires sophisticated decoding techniques. An optional solution for decoding convolutional codes is credited to Andrew Viterbi and is well known as the Viterbi algorithm.
The Viterbi algorithm is a recursive solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process observed in memory-less noise. Viterbi decoding is not restricted to convolutional codes, but can be applied to other sequence estimation problems such as channel equalizers. Decoding of convolutional codes requires making probability decisions based on a sequence of received bits rather than on an individual bit-by-bit basis. The basic operation of the Viterbi decoder is to select the path through a trellis, in the presence of noise, that represents the most likely sequence that was generated by a convolutional encoder.
The Viterbi algorithm makes use of the recurrent properties of convolutional codes to provide an efficient solution to this problem. At each symbol period the algorithm generates a metric, a measure of probability, for each branch. The best path of each state is then determined by examining the accumulated metrics from all paths entering the state and selecting the one with the best metric. The other paths are discarded. Therefore, paths with errors will accumulate lower metrics and therefore be discarded leaving only the path that represents the sequence which was most likely generated by the encoder.
To implement the Viterbi algorithm, a plurality of add/compare/select (ACS) operations must be performed to calculate the best path to each state. In today's central processing unit (CPU) architectures which implement the Viterbi algorithm, sequential processing is utilized to perform the ACS operations. In a CPU approach, a plurality of sequential memory fetches, addition, storage and comparison operations must be executed. The sequential operation limits data throughput due to the high number of instructions needed per symbol or data bit.
Each path or branch has a unique value or metric which is represented by a positive or negative multi-bit binary value. Each path metric P and branch metric B is defined as a measure of distance determined by some form of comparison between a received symbol and a corresponding path or branch in a trellis. As used herein, the term pair “old” and “new” are convenient abbreviations to distinguish successive time points j−1, j, j+1, such as, for example, “old”=“j−1” and “new”=“j” or, for example, “old”=“j” and new=“j+1”. Indices i and j can be combined with integer numbers by addition (“+”), subtraction (“−”), multiplication (“*”), and division (“/”). For convenience, the multiplication symbol “*” can be left out. For example, 2i with i=2 equals 2*2=4. Relations of the type “a>b” and “a<b” have the logical values true (e.g., for 3>2) or false (e.g., for 3<2). The calculation operation for path metrics P and branch metrics B is not relevant to the present invention and will not be further discussed since metric calculation is well documented in existing literature.
FIG. 1
illustrates a prior art example of a trellis diagram for an N=16 state code. Blocks
41
,
42
, and
43
indicate first, second and third pluralities of path metrics {P (n, j−1) }, {P (n, j)} and {P (n, j+1)} (n=0 to N−1=15) for successive time points j−1, j, and j+1, respectively. Pluralities are illustrated by { }. Indices n are intended to be cyclical, for example, 8+8=16 is considered as 0; 8+9=1 and so on. For simplicity, indices j−1, j, and j+1 are not shown inside the blocks. N is the number of possible states for a convolutional code with K coefficients and is generally N=2
K−1
. Index n is also given as 2i, 2i+1, 2i+2 and so on for P (n, j−1) (block
41
), as i, i+1 and so on for P (n, j) (block
42
), and as i/2, i/2+1 and so on for P (n, j) (block
43
). Even index i goes from 0 to N-2. Lines between blocks
41
,
42
and
43
indicate the transitions of path metrics P (j−1) to P (j) and to P (j+1). In a representative example, butterfly
44
(bold lines) between block
41
and
42
, symbolizes the transition of old path metrics P (j−1) to new path metrics P (j). For convenience of explanation for i=2, encircled reference numbers
91
-
95
point to P (2i, j−1)=P (4, j−1
1
), P (2i+1, j−1)=P (5, j−1) of block
41
, to P (i, j)=P (2, j), P (i+N/2, j)=P (10, j) of block
42
, and to a branch metric B (i, j), respectively. N/2 butterflies (e.g.,
8
) are needed to transform {P (n, j−1)} to {P (n, j)}. As an example, and not intended to be limiting, the calculation for butterfly
44
will be explained in detail in connection with FIG.
2
.
FIG. 2
illustrates a simplified flow diagram of a prior art calculation method for implementing the Viterbi algorithm. Old metrics P (2i, j−1) on line
91
and P (2i+1, j−1) on line
92
(cf. encircled numbers in
FIG. 1
) are combined with +B (i, j) at line
95
to obtain new path metrics P (i, j) at line
93
and P (i+N/2, j) at line
94
. Block
11
illustrates that + B (i, j) is inverted to − B (i, j). As mentioned above, the Viterbi algorithm comprises the steps of adding (A) (blocks
12
,
14
,
16
, and
18
), comparing (C) (blocks
22
and
24
), and selecting (S) (blocks
32
and
34
).
(A) In the step of adding, block
12
provides P (2i, j−1)+B (i, j) at line
13
, block
14
provides P (2i+1, j−1)−B (i, j) at line
15
, block
16
provides P (2i, j−1)−B (i, j) at line
17
, and block
18
provides P (2i+1, j−1)+B (i, j) at line
19
. This resulting sums P+B are communicated to comparators
22
and
24
.
(C) In the step of comparing, block
22
makes a decision D (i, j). D (i, j) becomes D (i, j)=0 for a true relation:
P
(2
i, j
−1)+
B
(
i, j
)>P (2
i+
1,
j−
1)−
B
(
i, j
). (1)
Otherwise, D (i, j) becomes D (i, j)=1 for a true relation:
P (
2
i, j−
1)+
B
(
i, j
)<
P
(2
i+
1
, j−
1)−
B
(
i, j
). (2)
Relations (
2
) and (
3
) differ only by the “>,<”-symbols, so that the logical values true and false are inverted. Block
24
makes decision D (i+N/2, j) which becomes D (i+N/2, j)=0 for a true relation
P
(2
i, j
−1)−
B
(
i, j
)>
P
(2
i+
1
, j
−1)+
B
(
i,j
) (3)
The decision is D (i+N/2, j)=1 for a true relation
P
(2
i, j
−1)−
B
(
i, j
)<
P
(2
i+
1
, j−
1)+
B
(
i,j
) (4)
Relations (
4
) and (
5
) differ also only by the “>,<”-symbols. Decisions D (i, j) and D (i+N/2, j) are communicated to blocks
32
and
34
via control lines
36
and
38
, respectively.
(S) In the step of selecting, block
32
provides new
P
(
i, j
)=
P
(2
i, j
−1)+
B
(
i, j
) for
D
(
i, j
)=0 (5)
(left side of (
2
) and (
3
)) or provides new
P
(
i, j
)=
P
(2
i+
1
, j
−1)−
B
(
i, j
) for
D
(
i, j
)=1 (6)
(right side
Baron Natan
Salant Yoram
Zarubinsky Michael
Elmore Reba I.
Marc McDieunel
Motorola Inc.
LandOfFree
Apparatus and method for implementing viterbi butterflies does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for implementing viterbi butterflies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for implementing viterbi butterflies will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531539