US5329537A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of maximum likelihood decoding with sub-sampled decoding trellis, and corresponding decoding device
Assignee: Telediffusion de France ets Public de Diffusion
•
Filing: 1993-01-21
•
Granted: 1994-07-12
•
Expires: 2013-01-21
Abstract
Abstract Decoding apparatus provides the maximum likelihood decoding of a sequence of samples of the type implementing a Viterbi type of decision algorithm that defines an initial decoding trellis. Sub-sampling apparatus sub-samples the initial trellis by a ratio p to preserve nodes corresponding to one sample out of p consecutive samples. This sub-sampling apparatus associates a p order antecedent node to each preserved node. Trace-back apparatus traces an optimal path back in the sub-sampled trellis by associating the p order antecedent node for each preserved node. The trace back apparatus designates at least the last two nodes of the optimal path. Over-sampling apparatus over-samples the designation of the last two nodes of the optimal path. The factor p is an integer greater than 1 selected so that there is a single path between a node and its p order antecedent in the initial trellis. Hence the bit rate is increased by a factor p, without loss of information.
Inventors
- 👤 Michel Alard
- 👤 Damien Castelain
- 👤 Jean-Francois Helard
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:13
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/41
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
239 words
A method for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in making a trace-back of an optimum path in said trellis, said method comprising the following steps: sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples and in associating, with each of the nodes preserved, an information element identifying its p order antecedent node in said initial trellis, the trace-back of an optimum path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, delivering an information element designating the last two nodes of said optimum path, over-sampling by a ratio p by association, with said information element designating the last two nodes of said optimum path, of a decoding sequence corresponding to said last two nodes as well as to all the p-1 intermediate nodes not preserved during said sub-sampling step, p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.
Claim 2
Independent Claim
239 words
A method for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in making a trace-back of an optimum path in said trellis, said method comprising the following steps: sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples and in associating, with each of the nodes preserved, an information element identifying its p order antecedent node in said initial trellis, the trace-back of an optimum path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, delivering an information element designating the last two nodes of said optimum path, over-sampling by a ratio p by association, with said information element designating the last two nodes of said optimum path, of a decoding sequence corresponding to said last two nodes as well as to all the p-1 intermediate nodes not preserved during said sub-sampling step, p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.
Claim 3
Dependent Claim
83 words
A decoding method according to claim 1, organized in decoding cycles, a cycle comprising at least one consecutive period, each period comprising the following successive operations: an operation for the writing, in said sub-sampled trellis, of the data elements associated with all the nodes corresponding to a preserved sample, at least two operations for the reading, in said sub-sampled trellis, of data elements associated with all the nodes corresponding to a sample, so as to carry out the trace-back on said optimum path.
Claim 4
Dependent Claim
27 words
A method according to claim 2, wherein the ratio between the number of reading operations and the number of writing operations is equal to 3 or 4.
Claim 5
Dependent Claim
218 words
Decoding apparatus for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in establishing a trace-back of an optimal path in said trellis, said apparatus comprising: sub-sampling means for sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples, the sub-sampling means associating, with each of the nodes preserved, its p order antecedent node; trace-back means for tracing back an optimal path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, the trace-back means delivering an information element designating at least the last two nodes of said optimal path; memory means for storing the sub-sampled trellis; and over-sampling means for over-sampling the information element delivered by said trace-back means of an optimal path, p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.
Claim 6
Dependent Claim
218 words
Decoding apparatus for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in establishing a trace-back of an optimal path in said trellis, said apparatus comprising: sub-sampling means for sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples, the sub-sampling means associating, with each of the nodes preserved, its p order antecedent node; trace-back means for tracing back an optimal path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, the trace-back means delivering an information element designating at least the last two nodes of said optimal path; memory means for storing the sub-sampled trellis; and over-sampling means for over-sampling the information element delivered by said trace-back means of an optimal path, p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.
Claim 7
Dependent Claim
74 words
A device according to claim 4, wherein said sub-sampling means comprise a bank of 2.sup.ν registers, ν being the length of constraint of said convolutional code, each comprising p sets of ν flip-flops, said sets of ν flip-flops being interconnected in accordance with the model defined by said initial trellis, so that the outputs of said registers respectively deliver the p order antecedent of each of the 2.sup.ν nodes corresponding to a preserved sample.
Claim 8
Dependent Claim
49 words
A device according to claim 4, wherein said memory means comprises a circular random-access memory organized into words of 2.sup.ν.ν bits where ν is the length of constraint of said convolutional code, a word containing all the information elements associated with each of the nodes corresponding to a sample.
Claim 9
Dependent Claim
48 words
A device according to claim 6, wherein said trace-back means comprise means for the addressing of said memory delivering a set of at least two words, and means for the selection in each of said words, of the information corresponding to the node belonging to the optimal path.
Claim 10
Dependent Claim
52 words
A device according to claim 4, wherein said over-sampling means include a transcoding table associating, with an information element designating the at least last two nodes of said optimal path, a decoding sequence corresponding to said two nodes and to the set of the p-1 intermediate nodes not preserved during the sub-sampling.
Claim 11
Dependent Claim
29 words
A device according to claim 8, wherein said over-sampling means comprise serializing means, delivering said decoding sequence at a rate equal to that of the arrival of said samples.
Claim 12
Dependent Claim
11 words
A device according to claim 4, implanted in an integrated circuit.
References Cited (Backward Citations)
US4905317A
Cited
US4823346A
Cited
US5042036A
Cited
US5128967A
Cited
US5056117A
Cited
US5185747A
Cited
US5216694A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-07-11 | 1998-01-10 | 1998-07-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-07-11 | 2002-01-10 | 2002-07-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-07-11 | 2006-01-10 | 2006-07-12 | $7700.00 | Window Closed / Lapsed |