Binary cyclic-gap constant weight codes with low-complexity encoding and decoding

Abstract In this paper, we focus on the design of binary constant weight codes that admit low-complexity encoding and decoding algorithms, and that have size $$M=2^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:msup> </mml:mrow> </mml:math> so that codewords can conveniently be labeled with binary vectors of length k . For every integer $$\ell \ge 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , we construct a $$(n=2^\ell , M=2^{k_{\ell }}, d=2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>ℓ</mml:mi> </mml:msup> <mml:mo>,</mml:mo> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msub> </mml:msup> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> constant weight code $${{{\mathcal {C}}}}[\ell ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>[</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> of weight $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> by encoding information in the gaps between successive 1’s of a vector, and call them as cyclic-gap constant weight codes. The code is associated with a finite integer sequence of length $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> satisfying a constraint defined as anchor-decodability that is pivotal to ensure low complexity for encoding and decoding. The time complexity of the encoding algorithm is linear in the input size k , and that of the decoding algorithm is poly-logarithmic in the input size n , discounting the linear time spent on parsing the input. Both the algorithms do not require expensive computation of binomial coefficients, unlike the case in many existing schemes. Among codes generated by all anchor-decodable sequences, we show that $${{{\mathcal {C}}}}[\ell ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>[</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> has the maximum size with $$k_{\ell } \ge \ell ^2-\ell \log _2\ell + \log _2\ell - 0.279\ell - 0.721$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msub> <mml:mo>≥</mml:mo> <mml:msup> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mi>ℓ</mml:mi> <mml:msub> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:msub> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>ℓ</mml:mi> <mml:mo>-</mml:mo> <mml:mn>0.279</mml:mn> <mml:mi>ℓ</mml:mi> <mml:mo>-</mml:mo> <mml:mn>0.721</mml:mn> </mml:mrow> </mml:math> . As k is upper bounded by $$\ell ^2-\ell \log _2\ell +O(\ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>ℓ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mi>ℓ</mml:mi> <mml:msub> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msub> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> information-theoretically, the code $${{{\mathcal {C}}}}[\ell ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>[</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> is optimal in its size with respect to two higher order terms of $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> . In particular, $$k_\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msub> </mml:math> meets the upper bound for $$\ell =3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> and one-bit away for $$\ell =4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> . On the other hand, we show that $${{{\mathcal {C}}}}[\ell ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>[</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> is not unique in attaining $$k_{\ell }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>ℓ</mml:mi> </mml:msub> </mml:math> by constructing an alternate code $$\mathcal{{\hat{C}}}[\ell ]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow>