Capacity achieving code constructions for two classes of (d,k) constraints

DOI10.1109/TIT.2006.876224MaRDI QIDQ3547581zbMATH OpenOpenAlexFDO

Authors Yogesh Sankarasubramaniam, Steven W. McLaughlin

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0411006

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Source coding (94A29)

Abstract: In this paper, we present two low complexity algorithms that achieve capacity for the noiseless (d,k) constrained channel when k=2d+1, or when k-d+1 is not prime. The first algorithm, called symbol sliding, is a generalized version of the bit flipping algorithm introduced by Aviran et al. [1]. In addition to achieving capacity for (d,2d+1) constraints, it comes close to capacity in other cases. The second algorithm is based on interleaving, and is a generalized version of the bit stuffing algorithm introduced by Bender and Wolf [2]. This method uses fewer than k-d biased bit streams to achieve capacity for (d,k) constraints with k-d+1 not prime. In particular, the encoder for (d,d+2^m-1) constraints, 1le m<infty, requires only m biased bit streams.

Recommendations

• On the capacity of two-dimensional run-length constrained channels
• The construction of M-ary (d,∞) codes that achieve capacity and have the fewest number of encoder states
• Sliding-Block Decodable Encoders Between&lt;tex&gt;$(d,k)$&lt;/tex&gt;Runlength-Limited Constraints of Equal Capacity
• On runlength codes
• A practical method for approaching the channel capacity of constrained channels

Cited in

(11)

• Consolidation for compact constraints and Kendall tau LP decodable permutation codes
• An Improvement to the Bit Stuffing Algorithm
• Bit-Stuffing Algorithms and Analysis for Run-Length Constrained Channels in Two and Three Dimensions
• Optimal Parsing Trees for Run-Length Coding of Biased Data
• The construction of M-ary (d,∞) codes that achieve capacity and have the fewest number of encoder states
• scientific article; zbMATH DE number 1096545 (Why is no real title available?)
• Maximizing the Shannon Capacity of Constrained Systems with Two Constraints
• Efficient coding schemes for the hard-square model
• scientific article; zbMATH DE number 2135156 (Why is no real title available?)
• Efficient code constructions for certain two-dimensional constraints
• A new construction for n-track (d, k) codes with redundancy

This page was built for publication: Capacity achieving code constructions for two classes of (d,k) constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547581)