US5870414A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for encoding and decoding digital signals
Assignee: McGill University
•
Filing: 1996-09-19
•
Granted: 1999-02-09
•
Expires: 2016-09-19
Abstract
Abstract A method of encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, comprises the steps of successively encoding respective first portions using a trellis code to produce a corresponding sequence of trellis-encoded words, using each of the trellis-coded words to select one of a plurality of subcodes of a block code, and using the selected subcode to encode the corresponding second portion of the digital word corresponding sequentially to the trellis-coded word used to select the subcode, thereby providing a sequence of codewords corresponding to the sequence of digital words. After transmission and/or storage, a sequence of codeword vectors comprising the codewords and noise may be decoded by operating upon each of the sequence of codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and associating with each of the estimated first portions the corresponding estimated second portion, thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded. The block code may comprise a Kerdock code, the subcodes being cosets of the Reed-Muller code. The decoder may then comprise a Fast Hadamard Transform unit and a Viterbi algorithm decoder.
Inventors
- 👤 Jean-Paul Chaib
- 👤 Harry Leib
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:27
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; H03; H03M; H03M13/00; H03M13/25; H03M13/251; H03M13/253; H03M13/256; H03M13/29; H03M13/37; H03M13/39; H03M13/3961; H03M13/41; H04L1/0041; H04L1/0045; H04L1/0054; H03M13/03; H03M13/05; H03M13/13; H03M13/136
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
271 words
A method of encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, supplying the sequence of codewords to a transmission or storage medium, extracting a corresponding sequence of codeword vectors from the transmission or storage medium, and decoding the sequence of codeword vectors to extract the originally-encoded sequence of digital words; the encoding comprising the sequential steps of: using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and encoding each second portion of the digital words using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion; the decoding comprising the steps of; operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and associating with each of the estimated first portions the corresponding estimated second portion thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 2
Independent Claim
271 words
A method of encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, supplying the sequence of codewords to a transmission or storage medium, extracting a corresponding sequence of codeword vectors from the transmission or storage medium, and decoding the sequence of codeword vectors to extract the originally-encoded sequence of digital words; the encoding comprising the sequential steps of: using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and encoding each second portion of the digital words using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion; the decoding comprising the steps of; operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and associating with each of the estimated first portions the corresponding estimated second portion thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 3
Dependent Claim
15 words
A method as claimed in claim 1, wherein the trellis code is a convolutional code.
Claim 4
Dependent Claim
23 words
A method as claimed in claim 1, wherein the block code comprises a Kerdock code partitioned into said cosets of a Reed-Muller code.
Claim 5
Dependent Claim
51 words
A method as claimed in claim 1, wherein the second portions are encoded by operating upon each second portion using a Reed-Muller code and adding to each Reed-Muller encoded word a coset leader, the coset leaders being selected by mapping the trellis-encoded words to respective coset leaders of the Reed-Muller code.
Claim 6
Dependent Claim
45 words
A method as claimed in claim 1, wherein the step of encoding each second portion comprises the steps of using the trellis encoded word to select one of the cosets of the Reed-Muller code and using the selected coset to operate upon the second portion.
Claim 7
Dependent Claim
28 words
A method as claimed in claim 1, wherein the decoding is performed using a Fast Hadamard Transform for each subcode and the trellis decoder uses a Viterbi algorithm.
Claim 8
Independent Claim
123 words
A method of encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, comprising the sequential steps of: using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and encoding each second portion of the digital words using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion.
Claim 9
Independent Claim
123 words
A method of encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, comprising the sequential steps of: using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and encoding each second portion of the digital words using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion.
Claim 10
Dependent Claim
15 words
A method as claimed in claim 7, wherein the trellis code is a convolutional code.
Claim 11
Dependent Claim
23 words
A method as claimed in claim 7, wherein the block code comprises a Kerdock code partitioned into said cosets of a Reed-Muller code.
Claim 12
Dependent Claim
51 words
A method as claimed in claim 7, wherein the second portions are encoded by operating upon each second portion using a Reed-Muller code and adding to each Reed-Muller encoded word a coset leader, the coset leaders being selected by mapping the trellis-encoded words to respective coset leaders of the Reed-Muller code.
Claim 13
Dependent Claim
44 words
A method as claimed in claim 7, wherein the step of encoding each second portion comprises the steps of using the trellis-encoded word to select one of the cosets of the Reed-Muller code and using the selected coset to operate upon the second portion.
Claim 14
Dependent Claim
28 words
A method as claimed in claim 7, wherein the decoding is performed using a Fast Hadamard Transform for each subcode and the trellis decoder uses a Viterbi algorithm.
Claim 15
Independent Claim
280 words
A method of decoding a sequence of codeword vectors formed by encoding a sequence of digital words, each having a first portion and a second portion, by the sequential steps of, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words, using each trellis-encoded word to select a corresponding one of a plurality of subcodes of a block code each comprising a coset of a Reed-Muller code, and using the selected subcode to encode the second portion of the corresponding digital word; the method of decoding comprising the steps of: operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and associating with each of the estimated first portions the corresponding estimated second portion thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded, wherein the step of operating upon each of the codeword vectors includes the steps of applying to each codeword vector a coset leader for each of the cosets, and performing a Fast Hadamard Transform upon the resulting vector, and the step of operating upon the sequence of likelihood metrics and associated estimated second portions comprises applying a Viterbi algorithm thereto.
Claim 16
Independent Claim
280 words
A method of decoding a sequence of codeword vectors formed by encoding a sequence of digital words, each having a first portion and a second portion, by the sequential steps of, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words, using each trellis-encoded word to select a corresponding one of a plurality of subcodes of a block code each comprising a coset of a Reed-Muller code, and using the selected subcode to encode the second portion of the corresponding digital word; the method of decoding comprising the steps of: operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; using a trellis decoder, operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and associating with each of the estimated first portions the corresponding estimated second portion thereby providing a sequence of output digital words corresponding to the sequence of digital words originally encoded, wherein the step of operating upon each of the codeword vectors includes the steps of applying to each codeword vector a coset leader for each of the cosets, and performing a Fast Hadamard Transform upon the resulting vector, and the step of operating upon the sequence of likelihood metrics and associated estimated second portions comprises applying a Viterbi algorithm thereto.
Claim 17
Dependent Claim
292 words
Apparatus for encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, supplying the sequence of codewords to a transmission or storage medium, extracting a corresponding sequence of codeword vectors from the transmission or storage medium, and decoding the sequence of codeword vectors to extract the originally-encoded sequence of digital words; the apparatus comprising an encoder comprising: a trellis code unit for successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; a block code unit responsive to the trellis-encoded words for encoding respective second portions of the digital words to provide codewords from selected ones of subcodes of the block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion; the apparatus further comprising a decoding unit comprising; means for operating upon each of the sequence of codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; a trellis decoder unit having means for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 18
Dependent Claim
292 words
Apparatus for encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, supplying the sequence of codewords to a transmission or storage medium, extracting a corresponding sequence of codeword vectors from the transmission or storage medium, and decoding the sequence of codeword vectors to extract the originally-encoded sequence of digital words; the apparatus comprising an encoder comprising: a trellis code unit for successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; a block code unit responsive to the trellis-encoded words for encoding respective second portions of the digital words to provide codewords from selected ones of subcodes of the block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion; the apparatus further comprising a decoding unit comprising; means for operating upon each of the sequence of codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct; a trellis decoder unit having means for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 19
Dependent Claim
183 words
Apparatus as claimed in claim 14, wherein the trellis code unit comprises a plurality of input ports corresponding to the bits of said first portion of the digital signal, each for receiving a respective one of said bits, a corresponding plurality of delay elements each having an input connected to a respective one of the plurality of input ports, a plurality of summing devices each having a first input connected to an output of a respective one of the plurality of delay elements and an output connected to a respective one of a corresponding plurality of inputs of the selector means, the one of said plurality of delay elements connected to the first of the input ports having its output connected to a second input of the one of said summing devices having its first input connected to the last of the input ports and, by way of a further delay element, to a further input of the selector means preceding its plurality of inputs, each of the delay elements having a delay substantially equal to the duration of a said digital word.
Claim 20
Dependent Claim
67 words
Apparatus as claimed in claim 14, wherein the block code unit comprises a Reed-Muller encoder for encircling the second portions of the digital words to provide a sequence of Reed-Muller encoded words, selector means for mapping the trellis-encoded words to coset leaders of cosets of the Reed-Muller code, and a summing device for summing each coset leader with the corresponding Reed-Muller encoded word to provide said codeword.
Claim 21
Dependent Claim
15 words
Apparatus as claimed in claim 16, wherein the trellis decoder comprises a Viterbi algorithm decoder.
Claim 22
Dependent Claim
40 words
Apparatus as claimed in claim 14, wherein the block code unit comprises means responsive to the trellis-encoded word for selecting one of said cosets of the Reed-Muller code and using the selected coset to operate upon the corresponding second portion.
Claim 23
Dependent Claim
78 words
Apparatus as claimed in claim 14, wherein, in the decoding unit, the means for operating upon each of the sequence of codeword vectors comprises means for combining with each codeword vector each of the coset leaders and Fast Hadamard Transform means for operating upon the vectors resulting from such combination to produce said estimated decoded second portion and the metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct.
Claim 24
Dependent Claim
141 words
Apparatus for encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, comprising: a trellis code unit for successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and a block code unit for encoding respective second portions of the digital words to provide codewords from the selected ones of subcodes of the block code, the block code unit using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion.
Claim 25
Dependent Claim
141 words
Apparatus for encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, comprising: a trellis code unit for successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; and a block code unit for encoding respective second portions of the digital words to provide codewords from the selected ones of subcodes of the block code, the block code unit using one of a plurality of subcodes of a block code, each subcode comprising a coset of a Reed-Muller code, the coset used for a particular second portion being determined by the trellis-encoded word obtained by encoding the corresponding first portion.
Claim 26
Dependent Claim
67 words
Apparatus as claimed in claim 20, wherein the block code unit comprises a Reed-Muller encoder for encoding the second portions of the digital words to provide a sequence of Reed-Muller encoded words, selector means for mapping the trellis-encoded words to coset leaders of cosets of the Reed-Muller code, and a summing device for summing each coset leader with the corresponding Reed-Muller encoded word to provide said codeword.
Claim 27
Dependent Claim
81 words
Apparatus as claimed in claim 20, wherein the trellis encoder comprises a plurality of input ports and a corresponding plurality of delay elements equal in number to the number of bits in said first portion, each delay element having a delay equal to the duration of a said digital word, the input ports being connected directly to a first set of inputs of the selector unit and via the delay elements to a second set of inputs of the selector unit.
Claim 28
Dependent Claim
182 words
Apparatus as claimed in claim 20, wherein the trellis encoder comprises a plurality of input ports corresponding to the bits of said first portion of the digital signal, each for receiving a respective one of said bits, a corresponding plurality of delay elements each having an input connected to a respective one of the plurality of input ports, a plurality of summing devices each having a first input connected to an output of a respective one of the plurality of delay elements and an output connected to a respective one of a corresponding plurality of inputs of the selector means, the one of said plurality of delay elements connected to the first of the input ports having its output connected to a second input of the one of said summing devices having its first input connected to the last of the input ports and, by way of a further delay element, to a further input of the selector means preceding its plurality of inputs, each of the delay elements having a delay substantially equal to the duration of a said digital word.
Claim 29
Dependent Claim
40 words
Apparatus as claimed in claim 20, wherein the block code unit comprises means responsive to the trellis-encoded word for selecting one of said cosets of the Reed-Muller code and using the selected coset to operate upon the corresponding second portion.
Claim 30
Dependent Claim
280 words
A decoding apparatus for decoding codeword vectors produced by encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, the sequence of codewords being supplied to a transmission or storage medium, and extracted as a corresponding sequence of codeword vectors from the transmission or storage medium, the codewords being encoded by, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; using each trellis-encoded word to select a corresponding one a plurality of subcodes of a block code; and using the selected subcode to encode the second portion of the corresponding digital word, the block code comprising subcodes each constituted by one of a plurality of cosets of a Reed-Muller code; the decoding unit comprising; means for operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct, the decoder using a Fast Hadamard Transform; a trellis decoder unit having means using a Viterbi algorithm for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 31
Dependent Claim
280 words
A decoding apparatus for decoding codeword vectors produced by encoding a digital signal comprising a sequence of digital words, each comprising a first portion and a second portion, to provide a corresponding sequence of codewords, the sequence of codewords being supplied to a transmission or storage medium, and extracted as a corresponding sequence of codeword vectors from the transmission or storage medium, the codewords being encoded by, using a trellis code, successively encoding respective first portions of the sequence of digital words to produce a corresponding sequence of trellis-encoded words, each of the trellis-encoded words corresponding, in the sequence, to one of the digital words; using each trellis-encoded word to select a corresponding one a plurality of subcodes of a block code; and using the selected subcode to encode the second portion of the corresponding digital word, the block code comprising subcodes each constituted by one of a plurality of cosets of a Reed-Muller code; the decoding unit comprising; means for operating upon each of the codeword vectors using a decoder for each of the subcodes to produce, for each subcode, an estimated decoded second portion and a metric representing the likelihood that the estimated decoded second portion is correct, given that the assumed subcode is correct, the decoder using a Fast Hadamard Transform; a trellis decoder unit having means using a Viterbi algorithm for operating upon the sequence of likelihood metrics and the associated estimated second portions to provide a sequence of estimated first portions; and means for associating with each of the estimated first portions the corresponding estimated second portion thereby to provide a sequence of output digital words corresponding to the sequence of digital words originally encoded.
Claim 32
Dependent Claim
104 words
A decoding apparatus as claimed in claim 25, said second portions having been encoded by operating upon each second portion using the selected coset of the Reed-Muller code and adding to each Reed-Muller encoded word a coset leader, the coset leaders being selected by mapping the trellis-encoded words to respective coset leaders of the Reed-Muller code, wherein the means for operating upon each of the codeword vectors comprises means for combining with each codeword vector each of the coset leaders and Fast Hadamard Transform means for operating upon the vectors resulting from such combination to produce said estimated decoded second portion and said metric.
References Cited (Backward Citations)
US4295218A
Cited
US4761778A
Cited
US4939555A
Cited
US5142539A
Cited
US5151919A
Cited
US5218619A
Cited
US5230003A
Cited
US5321725A
Cited
US5353352A
Cited
US5742678A
Cited
US5651032A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |