Metric sifting in breadth-first decoding of convolutional coded data
AssigneeSharp Laboratories of America, Inc.
InventorAlan D. Kot
Life of this patent
Estimating the term…
Abstract
A metric sifting, i.e., sorting or selection, method which can efficiently provide a sorted set of survivor metrics during breadth-first reduced-search decoding of convolutional codes. The preferred embodiment efficiently implements the M algorithm by providing a sorted set of M survivor metrics using a linear-time (O(M)) number of comparisons. To obtain this efficiency, the method employs partitioning of branch metrics into implicitly sorted subsets, and employs efficient merging of these subsets. Compared to the prior art, the number of comparisons for metric sifting during M algorithm decoding of typical rate 1/n binary convolutional codes is reduced by 30-40%; more specifically, the number of comparisons is reduced from (2n-1)M-(n-1) to n(M-1)+2.sup.n -1.
Claims15
A method for metric sifting during breadth-first decoding of rate 1/n convolutional coded binary data using a partial search of a trellis or tree, in which a plurality M of paths and associated M path metrics are retained in storage at the end of each branch-decoding stage, each stage of the method comprising:
- forming 2.sup.n branch metrics that correspond to 2.sup.n possible labels of an n-bit branch, n being an integer greater than 1,
- extending each of the M path metrics to form 2M metrics, each extension using a branch metric that corresponds to the extended n-bit branch;
- grouping the 2M metrics into 2.sup.n subsets according to the n-bit label of the extended n-bit branch;
- merging the metrics to form a sorted output set containing M metrics which are the best M metrics from among the 2M metrics in the subsets;
- updating each of the M paths in storage with its corresponding metric from among said best M metrics;
- and
- concatenating with each of the M paths in storage its extended n-bit branch label.
A decoder for breadth-first decoding of rate 1/n convolutional coded binary data using a partial search of a trellis or tree, in which a plurality M of paths are retained at the end of each branch-decoding stage, the decoder including a metric sifting apparatus comprising:
- means for forming 2.sup.n branch metrics that correspond to the 2.sup.n possible labels of an n-bit branch, n being an integer greater than 1,
- means for extending each of the M path metrics to form 2M metrics, each extension using a branch metric that corresponds to the extended n-bit branch;
- means for grouping the 2M metrics into 2.sup.n subsets according to the n-bit label of the extended n-bit branch;
- means for merging the metrics to form a sorted output set containing M metrics which are the best M metrics from among the 2M metrics in the subsets;
- means for updating each of the M paths in storage with its corresponding metric from among said best M metrics;
- and
- means for concatenating with each of the M paths in storage its extended n-bit branch label.
A data communication or data storage system comprising:
- a source of 1/n convolutional coded binary data, n being an integer greater than 1;
- a transmitter transmitting the convolutional coded binary data over a communication or data storage channel;
- and
- a receiver including a decoder for breadth-first decoding of rate 1/n convolutional coded binary data using a partial search of a trellis or tree, in which a plurality M of paths are retained after each branch-decoding stage, the decoder including a metric sifting apparatus comprising:
- means for forming 2.sup.n branch metrics that correspond to the 2.sup.n possible labels of an n-bit branch, n being an integer greater than 1,
- means for extending each of the M path metrics to form 2M metrics, each extension using a branch metric that corresponds to the extended n-bit branch;
- means for grouping the 2M metrics into 2.sup.n subsets according to the n-bit label of the extended n-bit branch;
- means for merging the metrics to form a sorted output set containing M metrics which are the best M metrics from among the 2M metrics in the subsets;
- means for updating each of the M paths in storage with its corresponding metric from among said best M metrics;
- and
- means for concatenating with each of the M paths in storage its extended n-bit branch label.
Dependencies are inferred from the claim text.