Patent US6342060B1 successfully refreshed from Google Patents.
US5416787A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for encoding and decoding convolutional codes
Assignee: Toshiba Corp
•
Filing: 1992-07-29
•
Granted: 1995-05-16
•
Expires: 2012-07-29
Abstract
Abstract A reduction of the redundancy due to the use of the convolutional codes as the error correction codes is achieved by a convolutional encoding at an identical encoding rate and a puncture process using different puncture rates for different classes of the input signals classified by the error sensitivity of each bit. A reduction of the decoding delay time without deteriorating the decoding error rate is achieved by updating the survivor path by remaining bits of the selected survivor path for each state other than the oldest bit and an additional bit indicative of the each state to which a transition is made at the present stage of decoding. A reduction of a circuit size of a Viterbi decoder is achieved by using a single RAM for memorizing a path metric and a survivor path for each state at an immediately previous stage of decoding together in each word of the memory capacity. A reduction of the decoding error rate for the data block encoded by the convolutional encoding is achieved by using the (i+N+j) bits of decoder input signals containing entire N bits of the received signals, preceded by last i bits of the received signals and followed by first j bits of the received signals.
Inventors
- 👤 Tomoko Kodama
- 👤 Makoto Nakamura
- 👤 Tatsunori Saito
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 23:31
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0067; H04L1/0068; H04L1/0069; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/3961; H03M13/41; H03M13/65; H03M13/6502; H04L1/0045; H04L1/0054; H04L2001/0098
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
126 words
An apparatus for error correction encoding using convolutional codes, comprising: means for classifying input signals containing a plurality of bits into a plurality of classes according to an error sensitivity of each bit; encoder means for applying a convolutional encoding to the input signals classified into said plurality of classes, using an identical encoding rate for all the classes, to obtain encoded signals; and puncture means for carrying out a puncture process for puncturing selected bits of the encoded signals, using different puncture rates for the encoded signals corresponding to different ones of said plurality of classes, to obtain error correction encoded output signals in which different classes of the input signals are encoded at different encoding rates according to the error sensitivity of each bit.
Claim 2
Independent Claim
126 words
An apparatus for error correction encoding using convolutional codes, comprising: means for classifying input signals containing a plurality of bits into a plurality of classes according to an error sensitivity of each bit; encoder means for applying a convolutional encoding to the input signals classified into said plurality of classes, using an identical encoding rate for all the classes, to obtain encoded signals; and puncture means for carrying out a puncture process for puncturing selected bits of the encoded signals, using different puncture rates for the encoded signals corresponding to different ones of said plurality of classes, to obtain error correction encoded output signals in which different classes of the input signals are encoded at different encoding rates according to the error sensitivity of each bit.
Claim 3
Dependent Claim
46 words
The apparatus of claim 1, wherein the error correction encoded output signals contains bits corresponding to the different classes of the input signals in an ascending order of the puncture rates used in puncturing the encoded signals corresponding to the different classes of the input signals.
Claim 4
Dependent Claim
46 words
The apparatus of claim 1, wherein the error correction encoded output signals contains bits corresponding to the different classes of the input signals in a descending order of the puncture rates used in puncturing the encoded signals corresponding to the different classes of the input signals.
Claim 5
Dependent Claim
242 words
A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising: branch metric calculation means for calculating a branch metric for each state at a present stage of decoding; path metric memory means for memorizing a path metric for each state at an immediately previous stage of decoding; path memory means for memorizing a survivor path for each state at the immediately previous stage of decoding; ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, the path metric memorized in the path metric memory means, and the survivor path memorized in the path memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding, and updates the survivor path memorized in the path memory by remaining bits of the selected survivor path for each state at the present stage of decoding other than the oldest bit to be outputted and an additional bit indicative of said each state to which a transition is made at the present stage of decoding; and output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit means.
Claim 6
Dependent Claim
242 words
A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising: branch metric calculation means for calculating a branch metric for each state at a present stage of decoding; path metric memory means for memorizing a path metric for each state at an immediately previous stage of decoding; path memory means for memorizing a survivor path for each state at the immediately previous stage of decoding; ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, the path metric memorized in the path metric memory means, and the survivor path memorized in the path memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding, and updates the survivor path memorized in the path memory by remaining bits of the selected survivor path for each state at the present stage of decoding other than the oldest bit to be outputted and an additional bit indicative of said each state to which a transition is made at the present stage of decoding; and output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit means.
Claim 7
Dependent Claim
32 words
The Viterbi decoder of claim 4, wherein the additional bit is an encoder input bit which caused the transition to said each state at a time of encoding by the convolutional encoder.
Claim 8
Dependent Claim
221 words
A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising: branch metric calculation means for calculating a branch metric for each state at a present stage of decoding; memory means, formed by a single RAM having a memory capacity of 2 m words×(L+N) bits, where m is a memory length of the convolutional encoder, L is a truncation length for each survivor path used in the Viterbi decoder, and N is a number of bits used for expressing each path metric, for memorizing a path metric and a survivor path for each state at an immediately previous stage of decoding together in each word of the memory capacity: ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, and the path metric and the survivor path memorized in the memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding; and output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit.
Claim 9
Dependent Claim
221 words
A Viterbi decoder for decoding convolutional codes encoded by a convolutional encoder, comprising: branch metric calculation means for calculating a branch metric for each state at a present stage of decoding; memory means, formed by a single RAM having a memory capacity of 2 m words×(L+N) bits, where m is a memory length of the convolutional encoder, L is a truncation length for each survivor path used in the Viterbi decoder, and N is a number of bits used for expressing each path metric, for memorizing a path metric and a survivor path for each state at an immediately previous stage of decoding together in each word of the memory capacity: ACS circuit means for selecting a survivor path for each state at the present stage of decoding, by calculating the path metric for each state at the present stage of decoding from the branch metric calculated by the branch metric calculation means, and the path metric and the survivor path memorized in the memory means, the ACS circuit means outputs an oldest bit of the selected survivor path for each stage at the present stage of decoding; and output generation means for determining a decoded output according to the oldest bit of the selected survivor path for each state at the present stage of decoding outputted from the ACS circuit.
Claim 10
Dependent Claim
80 words
The Viterbi decoder of claim 6, wherein each stage of decoding includes 2×2 m processing timing units for carrying out a reading of the path metric and the survivor path for each state at the immediately previous stage of decoding memorized in the memory means to the ACS circuit means and a writing of the path metric and the survivor path for each state at the present stage of decoding obtained by the ACS circuit means into the memory means.
Claim 11
Dependent Claim
26 words
The Viterbi decoder of claim 6, wherein the ACS circuit means also updates the path metric and the survivor path memorized in the memory means simultaneously.
Claim 12
Dependent Claim
214 words
A communication system for transmitting data block containing K bits encoded by convolutional codes, comprising: a convolutional encoder for applying a convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in the convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits; memory means for memorizing the N bits of the encoded signals (R 0 , R 1 , . . . , R N-1 ), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R N-i+h (mod N), R N-i+h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), R h+j-1 (mod N)), where i is a positive integer, j is a non-negative integer, and h is a non-negative integer; and a Viterbi decoder for decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted from the memory means.
Claim 13
Dependent Claim
214 words
A communication system for transmitting data block containing K bits encoded by convolutional codes, comprising: a convolutional encoder for applying a convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in the convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits; memory means for memorizing the N bits of the encoded signals (R 0 , R 1 , . . . , R N-1 ), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R N-i+h (mod N), R N-i+h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), R h+j-1 (mod N)), where i is a positive integer, j is a non-negative integer, and h is a non-negative integer; and a Viterbi decoder for decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted from the memory means.
Claim 14
Dependent Claim
68 words
The communication system of claim 9, wherein the (i+N+j) bits of the decoder input signals comprises first i bits corresponding to last i bits of the encoded signals memorized in the memory means, next N bits corresponding to entire N bits of the encoded signals memorized in the memory means, and last j bits corresponding to first j bits of the encoded signals memorized in the memory means.
Claim 15
Dependent Claim
48 words
The communication system of claim 10, wherein the Viterbi decoder obtains a provisional final state by decoding the first i bits of the decoder input signals, and then decodes the next N+j bits of the decoder input signals by setting the provisional final state as an initial state.
Claim 16
Dependent Claim
39 words
The communication system of claim 11, wherein i is a number of stages required in the Viterbi decoder to obtain the provisional final state, and j is a truncation length for each survivor path used in the Viterbi decoder.
Claim 17
Dependent Claim
40 words
The communication system of claim 9, further comprising an interleaver for interleaving the encoded signals obtained by the convolutional encoder, and wherein the memory means comprises a deinterleaver for deinterleaving the memorized encoded signals before outputting the decoder input signals.
Claim 18
Independent Claim
211 words
A method of transmitting data block containing K bits encoded by convolutional codes, comprising the steps of: (a) applying the convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in a convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits; (b) memorizing the N bits of the encoded signals (R 0 , R 1 , . . , R N-1 ), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R N-i+h (mod N), R N-i+h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R h+j-1 (mod N)), where i is a positive integer, j is a non-negative integer, and h is a positive integer; and (c) decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted, by a Viterbi decoder.
Claim 19
Independent Claim
211 words
A method of transmitting data block containing K bits encoded by convolutional codes, comprising the steps of: (a) applying the convolutional encoding to the data block, in which the convolutional encoding starts from a state in which first m bits of the data block are entered in a convolutional encoder, and the convolutional encoding of remaining (K-m) bits of the data block are followed by the convolutional encoding of the first m bits of the data block, to obtain encoded signals containing N bits; (b) memorizing the N bits of the encoded signals (R 0 , R 1 , . . , R N-1 ), and outputting decoder input signals containing (i+N+j) bits arranged in an order of (R N-i+h (mod N), R N-i+h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R N-1+h (mod N) ; R h (mod N), R h+1 (mod N), . . . , R h+j-1 (mod N)), where i is a positive integer, j is a non-negative integer, and h is a positive integer; and (c) decoding the (i+N+j) bits of the decoder input signals in said order in which the decoder input signals are outputted, by a Viterbi decoder.
Claim 20
Dependent Claim
37 words
The method of claim 14, further comprising the step of interleaving the encoded signals obtained at the step (a), and wherein at the step (b), the memorized encoded signals are deinterleaved before outputting the decoder input signals.
Claim 21
Independent Claim
96 words
A method of decoding data encoded by a convolutional encoder having a memory length equal to m and capable of taking 2 m states; comprising the steps of: (a) memorizing the data; (b) calculating a likelihood for each of the 2 m states of the convolutional encoder to be an initial state, from at least a part of the data memorized at the step (a); and (c) decoding the data memorized at the step (a) by using the likelihood for each state to be the initial state calculated at the step (b), by a Viterbi decoder.
Claim 22
Independent Claim
96 words
A method of decoding data encoded by a convolutional encoder having a memory length equal to m and capable of taking 2 m states; comprising the steps of: (a) memorizing the data; (b) calculating a likelihood for each of the 2 m states of the convolutional encoder to be an initial state, from at least a part of the data memorized at the step (a); and (c) decoding the data memorized at the step (a) by using the likelihood for each state to be the initial state calculated at the step (b), by a Viterbi decoder.
Claim 23
Dependent Claim
110 words
The method of claim 16, wherein the step (b) further comprises the steps of: (b1) calculating a branch metric for each state with respect to each of last i bits of the data memorized at the step (a), where i is a positive integer; and (b2) calculating the path metric for each state with respect to each of the last i bits of the data memorized at the step (a), from the branch metric calculated at the step (b1), and outputting the path metric calculated for each state with respect to a last bit of the last i bits of the data memorized at the step (a) as the likelihood.
Claim 24
Independent Claim
77 words
An apparatus for decoding data encoded by a convolutional encoder capable of taking M states; comprising: Viterbi decoding means for decoding the data more than once with more than one different settings of an initial state of a trellis to be a different one of the M states of the convolutional encoder, to obtain a plurality off decoded outputs; and output determining means for selecting one of said plurality of decoded outputs of the Viterbi decoding unit.
Claim 25
Independent Claim
77 words
An apparatus for decoding data encoded by a convolutional encoder capable of taking M states; comprising: Viterbi decoding means for decoding the data more than once with more than one different settings of an initial state of a trellis to be a different one of the M states of the convolutional encoder, to obtain a plurality off decoded outputs; and output determining means for selecting one of said plurality of decoded outputs of the Viterbi decoding unit.
Claim 26
Dependent Claim
46 words
The apparatus of claim 18, wherein the Viterbi decoding means includes M Viterbi decoders, each of which has the initial state of the trellis set to be one of the M states different from the initial states used in other ones of the M Viterbi decoder.
Claim 27
Dependent Claim
52 words
The apparatus of claim 18, wherein the Viterbi decoding means includes: control means for setting an initial state of the trellis to be each of the M states sequentially; and a Viterbi decoder for decoding the data, for each setting of the initial state of the trellis set by the control means.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-15 | 1998-11-14 | 1999-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-15 | 2002-11-14 | 2003-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-15 | 2006-11-14 | 2007-05-16 | $7700.00 | Window Closed / Lapsed |