NDLI: Decoding concatenated codes using soft information

Content Provider	IEEE Xplore Digital Library
Author	Guruswami, V. Sudan, M.
Copyright Year	2002
Description	Author affiliation: Div. Comput. Sci., California Univ., Berkeley, CA, USA (Guruswami, V.)
Abstract	We present a decoding algorithm for concatenated codes when the outer code is a Reed-Solomon code and the inner code is arbitrary. "Soft" information on the reliability of various symbols is passed by the inner decodings and exploited in the Reed-Solomon decoding. This is the first analysis of such a soft algorithm that works for arbitrary inner codes; prior analyses could only, handle some special inner codes. Crucial to our analysis is a combinatorial result on the coset weight distribution of codes given only its minimum distance. Our result enables us to decode essentially up to the "Johnson radius" of a concatenated code when the outer distance is large (the Johnson radius is the "a priori list decoding radius" of a code as a function of its distance). As a consequence, we are able to present simple and efficient constructions of q-ary linear codes that are list decodable up to a fraction (1 - 1/q - /spl epsiv/) of errors and have rate /spl Omega/(/spl epsiv//sup 6/). Codes that can correct such a large fraction of errors have found numerous complexity-theoretic applications. The previous constructions of linear codes with a similar rate used algebraic-geometric codes and thus suffered from a complicated construction and slow decoding.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Math. Found. Comput. (TCMF) SIGACT EATCS Centre de Recherches Math., Univ. Montreal Math. Inf. Technol. & Complex Syst. (MITACS)
Starting Page	148
Ending Page	157
File Size	376413
Page Count	10
File Format	PDF
ISBN	0769514685
ISSN	10930159
DOI	10.1109/CCC.2002.1004350
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-05-21
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Decoding Concatenated codes Reed-Solomon codes Computer science Algorithm design and analysis Linear code Error correction codes Laboratories Binary codes Computational complexity
Content Type	Text
Resource Type	Article

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

Multitrial decoding of concatenated Reed-Solomon codes

Hermitian Codes As GRS Codes

Interleaved Reed-Solomon codes in concatenated code designs

Decoding algebraic geometric codes

Better Binary List Decodable Codes Via Multilevel Concatenation

Decoding binary expansions of low-rate Reed-Solomon codes far beyond the BCH bound

Reliability-based decoding of Reed-Solomon codes using their binary image

Concatenated runlength limited codes with soft-decision decoding

Bit Level Soft Decision decoding reed-solomon codes

Decoding concatenated codes using soft information

Similar Documents

Multitrial decoding of concatenated Reed-Solomon codes

Hermitian Codes As GRS Codes

Interleaved Reed-Solomon codes in concatenated code designs

Decoding algebraic geometric codes

Better Binary List Decodable Codes Via Multilevel Concatenation

Decoding binary expansions of low-rate Reed-Solomon codes far beyond the BCH bound

Reliability-based decoding of Reed-Solomon codes using their binary image

Concatenated runlength limited codes with soft-decision decoding

Bit Level Soft Decision decoding reed-solomon codes

Decoding concatenated codes using soft information