NDLI: The trellis complexity of convolutional codes

Content Provider	IEEE Xplore Digital Library
Author	McEliece, R.J. Wei Lin
Copyright Year	1963
Abstract	Convolutional codes have a natural, regular, trellis structure that facilitates the implementation of Viterbi's algorithm. Linear block codes also have a natural, though not in general a regular, "minimal" trellis structure, which allows them to be decoded with a Viterbi-like algorithm. In both cases, the complexity of an unenhanced Viterbi decoding algorithm can be accurately estimated by the number of trellis edge symbols per encoded bit. It would therefore appear that we are in a good position to make a fair comparison of the Viterbi decoding complexity of block and convolutional codes. Unfortunately, however, this comparison is somewhat muddled by the fact that some convolutional codes, the punctured convolutional codes, are known to have trellis representations which are significantly less complex than the conventional trellis. In other words, the conventional trellis representation for a convolutional code may not be the "minimal" trellis representation. Thus ironically, we seem to know more about the minimal trellis representation for block than for convolutional codes. We provide a remedy, by developing a theory of minimal trellises for convolutional codes. This allows us to make a direct performance-complexity comparison for block and convolutional codes. A by-product of our work is an algorithm for choosing, from among all generator matrices for a given convolutional code, what we call a trellis-canonical generator matrix, from which the minimal trellis for the code can be directly constructed. Another by-product is that in the new theory, punctured convolutional codes no longer appear as a special class, but simply as high-rate convolutional codes whose trellis complexity is unexpectedly small.
Sponsorship	IEEE Information Theory Society
Starting Page	1855
Ending Page	1864
Page Count	10
File Size	957488
File Format	PDF
ISSN	00189448
Volume Number	42
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-11-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Convolutional codes Viterbi algorithm Delay Block codes Code standards Hamming weight Length measurement Maximum likelihood decoding
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower bounds on trellis complexity of block codes

On unit constraint-length convolutional codes

Reliability-based code-search algorithms for maximum-likelihood decoding of block codes

Dimension/length profiles and trellis complexity of linear block codes

On Low-Complexity Maximum-Likelihood Decoding of Convolutional Codes

Trellis complexity and minimal trellis diagrams of lattices

Two-step trellis decoding of partial unit memory convolutional codes

A nonalgorithmic maximum likelihood decoder for trellis codes

BEAST decoding of block codes obtained via convolutional codes

The trellis complexity of convolutional codes

Similar Documents

Lower bounds on trellis complexity of block codes

On unit constraint-length convolutional codes

Reliability-based code-search algorithms for maximum-likelihood decoding of block codes

Dimension/length profiles and trellis complexity of linear block codes

On Low-Complexity Maximum-Likelihood Decoding of Convolutional Codes

Trellis complexity and minimal trellis diagrams of lattices

Two-step trellis decoding of partial unit memory convolutional codes

A nonalgorithmic maximum likelihood decoder for trellis codes

BEAST decoding of block codes obtained via convolutional codes

The trellis complexity of convolutional codes