Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2001-03-26
2002-09-10
Tokar, Michael (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S050000, C341S081000, C341S107000, C375S341000, C375S340000, C375S262000, C375S240000, C375S354000, C714S786000, C714S789000, C714S794000, C714S769000, C714S795000
Reexamination Certificate
active
06448910
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital signal processing, and more particularly to the mapping of a convolution encoder and a Viterbi decoder onto a dynamically re-configurable two-dimensional single instruction multiple data (SIMD) processor array architecture.
2. Description of Related Art
The field of digital signal processing (DSP) has grown dramatically in recent years and has quickly become a key component in many consumer, communications, medical, and industrial products. DSP technology involves the analyzing and processing of digital data in the form of sequences of ones and zeros. In the field of communications, analog signals are converted to such digital sequences for processing and transmission. During transmission, however, these digital sequences may be easily distorted by noise. In order to address this problem, digital data is often encoded before transmission. One form of encoding, known as convolution encoding, is widely used in digital communication and signal processing to protect transmitted data against noise, and its efficiency is well known in terms of error correction quality. In general, convolution encoding is a coding scheme that associates at least one encoded data element with each source data element to be encoded, this encoded data element being obtained by the modulo-two summation of this source data element with at least one of the previous source data elements. Thus, each encoded symbol is a linear combination of the source data element to be encoded and the previous source data elements.
In
FIG. 1A
, a schematic diagram of a standard convolution encoder with a code rate of one half is shown. For this type of encoder, two encoding outputs, a(t) and b(t), are transmitted for every input u(t). The encoder is shown to be comprised of two delay elements,
10
and
12
, and three exclusive-OR Boolean operators
20
,
22
, and
24
. As illustrated, an input u(t) is connected to a first delay element
10
, a first exclusive-OR operator
20
, and a second exclusive-OR operator
22
. The output u(t−1) of the first delay element
10
is connected to the input of the second delay element
12
and to the second exclusive-OR operator
22
. The output u(t−2) of the second delay element
20
is then connected to the first exclusive-OR operator
20
and to the third exclusive-OR operator
24
. The encoding outputs, a(t) and b(t), are then respectively taken from the outputs of the first exclusive-OR operator
20
and the third exclusive-OR operator
24
. It should be appreciated that there are four possible binary states of the encoder (u(t−1), u(t−2)), including state zero (00), state one (01), state two (10), and state three (11).
The encoding process of the described encoder may also be characterized by the finite state machine illustrated in FIG.
1
B. In this diagram, each circle is labeled with a binary representation of one of the four binary states of the encoder. In particular, this diagram provides binary representations for state zero
40
, state one
44
, state two
42
, and state three
46
. This diagram is further comprised of several arrows representing the respective transition paths taken into each particular state. In this example, a total of eight transition paths
30
,
31
,
32
,
33
,
34
,
35
,
36
, and
37
are illustrated. Each transition path also includes an input/output pair (u(t)/a(t), b(t)) uniquely identifying the conditions needed for that particular transition to occur.
For example, beginning at state zero
40
, there are two possible transition paths, including path
30
and path
31
. Path
30
depicts an input u(t) of zero that produces respective outputs a(t), b(t) of zero, zero (0/00), thereby causing the finite state machine to remain at state zero
40
(or 00). Path
31
depicts an input u(t) of one and respective outputs a(t), b(t) of one, one (1/11), thereby causing the finite state machine to transition to state two
42
(or 10). From state two
42
, there are two possible transition paths, including path
32
and path
37
. Path
32
depicts an input u(t) of one that produces respective outputs a(t), b(t) of one, zero (1/10), thereby causing the finite state machine to transition to state three
46
(or 11). Path
37
depicts an input u(t) of zero and respective outputs a(t), b(t) of zero, one (0/01), thereby causing the finite state machine to transition to state one
44
(or 01). The remaining transition paths follow in like manner.
In order to depict how the described encoder evolves over time, a trellis diagram is shown in
FIG. 1
C. As illustrated, this diagram is comprised of several nodes (denoted by dots) and transition paths (denoted by solid lines). Each column of nodes represents all states at a particular instant. In this particular example, five instants are described (corresponding to t=1 through t=5). Therefore, this trellis diagram can be regarded as illustrating the sequence of all possible state transition paths over five instants (where it is assumed that the initial state is state zero
40
). As a result, any given stream of input bits u(t) can be uniquely determined directly from its corresponding sequence of outputs, a(t) and b(t), and information derived from the encoder's trellis diagram. For example, if after four instants the observed noiseless outputs {a
1
(t)/b
1
(t), a
2
(t)/b
2
(t), a
3
(t)/b
3
(t), a
4
(t)/b
4
(t)} at a receiver are {11, 10, 10, 00}, then the corresponding input sequence {u
1
(t), u
2
(t), u
3
(t), u
4
(t)} is {1, 1, 0, 1} according to the trellis diagram shown in FIG.
1
C. In this example, it should be clear that the number of decoded input bits is determined directly from the number of instants traced back in a given trellis diagram. In practice, two trace-back approaches are used. In the first approach, the number of instants traced back in a trellis diagram is equal to the total number of bits in the entire bit stream (resulting in the decoding of the entire bit stream at once). In the second approach, a pre-determined number of instants is used resulting in the decoding of partial bit streams at a time.
In general, noise will occur during transmission. For example, if the observed output sequence is {10, 10, 10, 00}, the corresponding input sequence is unclear. Thus in practical applications, statistical decoding methods that account for such noise must be implemented. It should be noted that although each transition path
30
,
31
,
32
,
33
,
34
,
35
,
36
, and
37
described in
FIG. 1B
is included in the trellis diagram of
FIG. 1C
, for simplicity, only transition paths
30
and
31
are labeled.
In the presence of noise, the most commonly used approach to decode convolution codes is via the Viterbi algorithm. In particular, the Viterbi algorithm gives a binary estimation of each input u(t) coded at transmission. This estimation is determined by finding the most likely transition path of a given trellis with respect to the noisy output data (X(t), Y(t)) received by a decoder respectively corresponding to the originally encoded output data (a(t), b(t)). Each node of the trellis used during decoding contains an information element on the survivor path of the two possible paths ending at that particular node. The basic principle of the Viterbi algorithm consists in considering, at each node, only the most probable path as to enable easy trace-back operations on the trellis and hence to determine an a posteriori estimation of the value received several reception instants earlier.
The Viterbi algorithm involves the execution of a particular set of operations. First, a computation is made of the distances, also called branch metrics, between the received noisy output data (X(t), Y(t)) and the symbols (a(t), b(t)) corresponding to the required noiseless outputs of a particular state transition path. In particular these branch metric units are defined as:
Branch(
a
s
, b
s
)=
a
s
X
k
+b
s
Y
k
wher
Mai Lam T.
Morpho Technologies
O'Melveny & Myers LLP
Tokar Michael
LandOfFree
Method and apparatus for convolution encoding and viterbi... 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 and apparatus for convolution encoding and viterbi..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for convolution encoding and viterbi... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820989