Metric sifting in breadth-first decoding of convolutional coded

Details Metric sifting in breadth-first decoding of convolutional coded Metric sifting in breadth-first decoding of convolutional coded

1997-03-26

1999-05-04

Ghebretinsae, Temesghen

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

375265, 371 437, 371 438, H04L 2706, H04L 2302, G06F 1110

Patent

active

059011823

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
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.

REFERENCES:
patent: 3457562 (1969-07-01), Fano
patent: 4500994 (1985-02-01), McCallister et al.
patent: 4933956 (1990-06-01), Forney, Jr.
patent: 5229767 (1993-07-01), Winter et al.
patent: 5291499 (1994-03-01), Behrens et al.
patent: 5327439 (1994-07-01), Estola et al.
patent: 5384810 (1995-01-01), Amrany
patent: 5406570 (1995-04-01), Berrou et al.
patent: 5502735 (1996-03-01), Cooper
patent: 5539757 (1996-07-01), Cox et al.
patent: 5588028 (1996-12-01), Parizhsky
Forney Jr., G.D., "The Viterbi Algorithm," Proc. IEEE, vol. 61, pp. 268-278, Mar. 1973.
Wolf, J.K., "Efficient maximum likelihood decoding of linear block codes using a trellis," IEEE Trans. Inform. Theory, vol. IT-24, No. 1, pp. 76-80, Jan. 1978.
Anderson, J.B. and Mohan, S., "Sequential decoding algorithms: A survey and cost analysis," IEEE Trans. Commun., vol. COM-32, No. 2, pp. 169-176, Feb. 1984.
Fano, R.m., "A heuristic discussion of probabilistic decoding," IEEE Trans. Inform. Theory, vol. IT-9, pp. 64-74, Apr. 1963.
Anderson, J.B. and Mohan, S., "Architectures for Coding Algorithms," Chapter 7, Coding: An Algorithmic Approach, Kluwer, pp. 365-379, 1990.
Mohan, S. and Sood, A. K., "A multiprocessor architecture for the (M,L)-algorithm suitable for VLSI implementation," IEEE Trans. Commun., vol. COM-34, No. 12, pp. 1218-1224, Dec. 1986.
Simmons, S.J., "A nonsorting VLSi structure for implementing the (M,L) algorithm," IEEE J. Selected Areas Commun., vol. JSAC-6, pp. 538-546, Apr. 1988.
Kot, A.D., "A linear-time method for contender sifting in breadth-first decoding of error control codes," 1993 Canadian Conference on Electrical and Computer Engineering, Vancouver Canada, Sep. 1993, (Kot 93).
Knuth,D.E., The Art of Computer Programming: vol. III, Sorting and Searching, Addison Wesley, pp. 208-215, 1973.
Simmons, S.J., "Breadth-first decoding with adaptive effort," IEEE Trans. Commun., vol. COM-38, No. 1, pp. 3-12, Jan. 1990.
Kot, A.D., On the Construction, Dimensionality, and Decoding of Linear Block Code Trellises, Ph.D. Thesis, University of British Columbia, Dec., 1992.
Lin, C. F. and Anderson, J. B., "M-algorithm decoding of channel convolutional codes," Conf. on Information Science and Systems, Princeton University, Princeton, New Jersey, pp. 362-366, Mar. 1986.
Benelli, G. and Fantacci, R., "New detection algorithm with reduced complexity," IEE Proc., vol. 137, Pt. 1, No. 1, pp. 47-59, Feb. 1990.
Lee, W-T.; Chan, M-H.; Chen, L-G., and Lin, M-C., "A single-chip Viterbi decoder for a binary convolutional code using an adaptive algorithm," IEEE Trans. Consumer Electronics, vol. 41, No. 1, Feb. 1995.

Affiliated with

Also associated with

Rating

Metric sifting in breadth-first decoding of convolutional coded does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Metric sifting in breadth-first decoding of convolutional coded , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metric sifting in breadth-first decoding of convolutional coded will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1875578