Pulse or digital communications – Systems using alternating or pulsating current
Reexamination Certificate
2001-03-07
2004-12-14
Chin, Stephen (Department: 2634)
Pulse or digital communications
Systems using alternating or pulsating current
C375S341000, C714S795000
Reexamination Certificate
active
06831952
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for decoding an encoded data stream.
2. Description of the Prior Art
Bit errors can often arise when transmitting data across a medium, such as radio, infra-red, via a hard disk's magnetic head, etc. Accordingly, it is known to encode data prior to transmission so as to add redundancy to the original data before it is transmitted. A suitable decoder is then used when the data stream is received to decode the encoded data stream, with the redundancy providing some resilience to bit errors. Of course, the more redundancy added during encoding, the more bits that need to be transmitted, and accordingly, a balance is necessary between the amount of redundancy added, and the amount of resilience to bit errors achieved as a result of the addition of the redundancy.
One common encoding technique is often referred to as convolutional encoding, which produces an encoded data stream comprising a plurality of codes. Whenever the encoder receives an input to be encoded, e.g. a data bit, it generates a code dependent on the received input, and a number of previous inputs received by the encoder. A term called “constraint length” is used to indicate the number of inputs that a convolutional encoder uses in order to generate an output code. For example, if the constraint length “k” is 7, this means that the output code generated by the convolutional encoder is dependent on the current input, plus the previous 6 inputs. Accordingly, it will be appreciated that for each input, there are 2
k-1
previous states that the encoder could be in.
There are many different uses for the above type of encoding, for example in hard disk drives, mobile phones, and Digital Audio Broadcast (DAB) radio. One example of a standard relating to DAB is the ETSI (European Telecommunications Standard Institute) ETS 300 401 May 1997 (Second Edition) standard entitled “Radio Broadcasting Systems;Digital Audio Broadcasting (DAB) to mobile, portable and fixed receivers”. In DAB radio, the constraint length k of the encoder is 7, so, for each input bit, there are 64 states that the encoder could be in (based on the 6 previous input bits).
When an original sequence of data bits has been encoded to form an encoded data stream, it will be appreciated that a technique needs to be provided at the receiving end for decoding the data stream and using the redundancy therein to seek to correct any errors in the information received. One algorithm often used to perform such decoding is the Viterbi algorithm which is typically used to decode convolutionally encoded data streams. A general description of the Viterbi algorithm is given in the publication “Digital Communications” by John G. Proakis (Third Edition). McGraw-Hill Inc.
In accordance with the Viterbi technique, a table such as that illustrated in
FIG. 1
is generated, which has an entry for each of the 2
k-1
states, and which is updated upon receipt of each code in the encoded data stream, Hence, as illustrated in
FIG. 1
, each entry will have a field
20
identifying the state, a field
30
identifying a “metric” or score associated with that state, and a path history
40
giving an indication of a predetermined number of bits that are considered to be bits in the original data sequence assuming the associated state is the most likely state.
When each code is received, the metric
30
for each of the states must be updated, and the state with the “best” metric (e.g. typically the one with either the lowest or the highest value depending on the implementation) is selected as having the correct path. Accordingly, the oldest bit in that state's path history
40
is then output as the correct output bit for this stage.
To indicate how the metrics are typically updated for each state, reference will be made to
FIG. 2
, which indicates how a new state is related to a previous state. It will be appreciated that, assuming a particular state is correct, then when a new bit is received by the encoder, that bit will either be a logic zero value or a logic one value, and accordingly there are two possibilities as to the data used to generate the code output by the encoder. Due to the possibility of corruption of the signal, it will be appreciated that, when a code is received at the decoder, it is necessary to determine, for each state in the table
10
, the likelihood that that state represents the k-1 previous input bits used along with a new input bit to generate the code.
With reference to
FIG. 2
, this illustrates the possible states assuming the constraint length k is 4, and that accordingly three preceding input bits are used along with a new input bit to generate a code. On the left hand side of the diagram, it will be seen that all of the eight possible states of the three preceding bits are indicated. Considering the example of the old state being
001
, it will be appreciated that the data upon which the code generated by the encoder was based would either be
0010
or
0011
, i.e. the new bit can only be
0
or
1
. The decoder knows what the code generated by the encoder would have been had the bits in fact been
0010
or
0011
. and can accordingly compare those codes with the code received to determine the likelihood that the bits used to generate the transmitted code were in fact
0010
or
0011
. This comparison yields an update value (often referred to as a Hamming distance) which can be used to generate an updated score for the state.
As is also apparent from
FIG. 2
, although once the code has been processed, there are still the same set of states in the table
10
, the way in which these states are related to the old states is quite complex. For example, the new state
010
may have arisen from the previous states
001
or
101
, in both cases with the new bit received being a
0
. Hence, Hamming distances can be generated for each possibility based on comparing the code received with the code expected for
0010
and
1010
, respectively. Then the metric associated with the old state
001
is retrieved, and the corresponding Hamming distance is added to that metric, resulting in a possible updated metric. This process is repeated for the metric associated with the state
101
, whereby two possible metrics for the new state
010
have now been calculated. Whichever of the two possible metrics is deemed best (for example, the one with the smallest value if the Hamming distance is defined to increase as the match between the two codes gets worse) is selected, and used as the new metric for state
010
. In addition, the relevant bit is added to the relevant path history. For example, if state
010
is deemed to have arisen from state
001
, it can be seen that logic 0 value should be added to the path history for
001
. This path history is then copied to the state
010
as the new path history for that state. Alternatively, if state
010
is deemed to have arisen from state
101
, it can be seen that a logic 1 value should be added to the path history for state
101
, and this path history then copied to the state
010
as the new path history for that state.
The above process is performed for each of the states in the table 10, with the end result being that each of the metrics
30
and path histories are updated. Further, if the path history is already full, then the oldest bit in the path history associated with the state having the best metric may be output at this time as the bit considered to be the correct bit in the original data sequence.
Given the above description, it will be appreciated that for each state update, two metrics (often metrics from different states to the state being updated) need to be added to two Hamming distances (which are dependent on the code received) and the smaller of the two (assuming a smaller distance is better) is selected and then stored in association with the state being updated. Later, when output bits are required from the decoder, all of the metrics are compared, and the state with the best metric is
Francis Hedley James
Symes Dominic Hugo
Arm Limited
Chin Stephen
Ware Cicely
LandOfFree
System, method and computer program for decoding an encoded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method and computer program for decoding an encoded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and computer program for decoding an encoded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3309321