NDLI: Path partitions and forward-only trellis algorithms

Content Provider	IEEE Xplore Digital Library
Author	Xiao Ma Kavcic, A.
Copyright Year	1963
Abstract	This is a semitutorial paper on trellis-based algorithms. We argue that most decoding/detection algorithms described on trellises can be formulated as path-partitioning algorithms, with proper definitions of mappings from subsets of paths to metrics of subsets. Thereby, the only two operations needed are path-concatenation and path-collection, which play the roles of multiplication and addition, respectively. Furthermore, we show that the trellis structure permits the path-partitioning algorithms to be formulated as forward-only algorithms (with structures resembling the Viterbi (1967) algorithm), thus eliminating the need for backward computations regardless of what task needs to be performed on the trellis. While all of the actual decoding/detection algorithms presented here are rederivations of variations of previously known methods, we believe that the exposition of the algorithms in a unified manner as forward-only path-partitioning algorithms is the most intuitive manner in which to generalize the Viterbi algorithm. We also believe that this approach may, in fact, influence the practical implementation of the algorithms as well as influence the construction of other forward-only algorithms (e.g., byte-wise forward-only detection algorithms).
Sponsorship	IEEE Information Theory Society
Starting Page	38
Ending Page	52
Page Count	15
File Size	1104583
File Format	PDF
ISSN	00189448
Volume Number	49
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-01-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	Partitioning algorithms Signal processing algorithms Viterbi algorithm Decoding Iterative algorithms Detection algorithms Sum product algorithm Convolutional codes Error probability Intersymbol interference
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

Decoding algorithms for noncoherent trellis coded modulation

Iterative soft-QRD-M for turbo coded MIMO-OFDM systems

Limited search trellis decoding of convolutional codes

Iterative decoding of binary block and convolutional codes

How I learned to love the trellis

Joint detection/decoding algorithms for non-binary low-density parity-check codes over inter-symbol interference channels

A unified framework for finite-memory detection

New SISO decoding algorithms

Iterative Viterbi decoding, trellis shaping, and multilevel structure for high-rate parity-concatenated TCM

Path partitions and forward-only trellis algorithms

Similar Documents

Decoding algorithms for noncoherent trellis coded modulation

Iterative soft-QRD-M for turbo coded MIMO-OFDM systems

Limited search trellis decoding of convolutional codes

Iterative decoding of binary block and convolutional codes

How I learned to love the trellis

Joint detection/decoding algorithms for non-binary low-density parity-check codes over inter-symbol interference channels

A unified framework for finite-memory detection

New SISO decoding algorithms

Iterative Viterbi decoding, trellis shaping, and multilevel structure for high-rate parity-concatenated TCM

Path partitions and forward-only trellis algorithms