Keywords (1)

Academic
Publications
An improvement to the bit stuffing algorithm

An improvement to the bit stuffing algorithm,10.1109/TIT.2005.851764,IEEE Transactions on Information Theory,Sharon Aviran,Paul H. Siegel,Jack Keil Wo

An improvement to the bit stuffing algorithm   (Citations: 5)
BibTex | RIS | RefWorks Download
The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d, k) con- strained codes. Results show that the maximum av- erage rate of the bit stuffing code achieves capacity when k = d +1 or k = ∞, while it is suboptimal for all other (d, k) pairs. We propose a modification to the bit stuffing algorithm. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d, k) constraints.
Journal: IEEE Transactions on Information Theory - TIT , vol. 51, no. 8, pp. 2885-2891, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...A more recent work [8] modified BS by adding a controlled flipping of unconstrained bits before writing them...

    Sharon Aviranet al. Optimal Parsing Trees for Run-Length Coding of Biased Data

    • ...A more recent work [8] modified BS by adding a controlled flipping of unconstrained bits before writing them...

    Sharon Aviranet al. Optimal Parsing Trees for Run-Length Coding of Biased Data

    • ...<{[SECTION]}>[2] L. A. Bassalygo, V. A. Zinov’ev, V. V. Zyablov, M. S. Pinsker, and G...
    • ...In subsequent work, the bit stuffing [3] and bit flipping [2] algorithms were proposed to construct optimal and near-optimal codes using a -DT, where denotes the Bernoulli distribution with . Unlike the -DT, where is in general nonbinary, the -DT has the property that the output distribution is binary...
    • ...More recently, the bit flipping algorithm [2] was shown to improve bit stuffing rates for most constraints and additionally achieve (2,4) capacity...
    • ...It has been observed in [2] that optimal codes can be constructed for all using -DTs...
    • ...To meet this objective, we restrict ourselves to the use of a single distribution transformer as in bit stuffing, and show that a simple switching of bit stuffing phrase probabilities improves the encoding rates for several values of and .A s afirst step, we show how this idea leads to the recently proposed bit flipping algorithm [2], and then generalize to symbol sliding in Section III...
    • ...The aforementioned algorithm is precisely the bit flipping algorithm proposed by Aviran et al. [2]...
    • ...Recently, it was observed in [2] that with the use of multiple such DTs, optimal bit stuffing encoders could be constructed for all values of and . The idea is to generate several distinct i.i.d., biased bit streams, one each for a state in the FSTD that has two outgoing branches (see Fig. 2). Since the number of such states is for , we need precisely that many DTs to construct optimal codes in this fashion...
    • ...Our second construction was motivated by a recent generalization of bit stuffing proposed in [2], where biased bit streams are used to construct optimal codes for all constraints, . Here,...
    • ...They would also like to thank E. M. Kurtas for his help, support and insight into this problem, and S. Aviran for providing a copy of the submitted version of reference [2]...

    Yogesh Sankarasubramaniamet al. Capacity Achieving Code Constructions for Two Classes of (d, k)Constra...

    • ...The first algorithm, symbol sliding, is a generalized version of the bit flipping algorithm introd uced by Aviran et al [1]...
    • ...More recently, the bit flipping algorithm [1] was shown to improve...
    • ...Wolf [1] observed that with the use of multiple such DTs, one could, in theory, generate enough degrees of freedom to produce optimal (d,k) sequences for all 0 ≤ d < k. More precisely, k − d DTs were shown to be sufficient for any given ( d,k) constraint, k < ∞...
    • ...The algorithm described above is precisely the bit flipping a lgorithm proposed by Aviran et al [1]...
    • ...Recently, Wolf [1] observed that with the use of multiple such DTs, optimal bit stuffing encoders could be constructed for all values of d and k. The idea is to generate several distinct biased streams, one each for a state in the FSTD that has two outgoing branches (see Fig. 2). Since the number of such states is k − d for k < ∞, we need precisely that many DTs to construct optimal codes in this fashion...
    • ...Our second construction was inspired by a recent generalization of bit stuffing proposed by Wolf [1], where k − d biased bit streams are used to construct optimal (d,k) sequences for all k < ∞. Here, we observed that the factorization of certain charact eristic (d,k) polynomials could be used to construct optimal codes with fewer than k − d DTs...
    • ...The authors wish to thank Dr. Erozan M. Kurtas for his help, support and insight into this problem, and Sharon Aviran for providing a copy of reference [1]...

    Yogesh Sankarasubramaniamet al. Capacity Achieving Code Constructions for Two Classes of (d,k) Constra...

    • ...[3] algorithms for (d;k) constraints, we introduced the symbol sliding algorithm in...

    Yogesh Sankarasubramaniam. New Capacity-Approaching Codes for Run-Length-Limited Channels

Sort by: