index.html 16.3 KB
 Julie Blanc committed Sep 28, 2018 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213  Scientific math paper

An explicit formula for a weight enumerator of linear-congruence codes

Taro Sakurai

An explicit formula for a weight enumerator of linear-congruence codes is provided. This extends the work of Bibak and Milenkovic [IEEE ISIT (2018) 431–435] addressing the binary case to the non-binary case. Furthermore, the extension simplifies their proof and provides a complete solution to a problem posed by them.

weight enumerator, code size, linear-congruence code, exponential sum

August 29, 2018.

2010 Mathematics Subject Classification: 94B60 (05A15, 11L15)

Source: https://arxiv.org/abs/1808.09365v1

Introduction

Throughout this article, n and m denote positive integers, b denotes an integer and $\mathbb{Z}_q ≔ \{0, 1, \dotsc, q-1\} \subset \mathbb{Z}$ for a positive integer q. We will use n for a code length, m for a modulus, b for a defining parameter of a code and q for a code alphabet.

Definition

Let $a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$ and b ∈ ℤ. The set C of all the solutions $x = (x_1, \dotsc, x_n) \in \mathbb{Z}_q^n$ for a linear congruence equation $$\label{eq: ax = b} a\cdot x \equiv b \pmod m$$ is said to be a linear-congruence code where $a\cdot x ≔ a_1x_1 + \dotsb + a_nx_n$. A linear-congruence code C is called binary when q = 2.

Several deletion-correcting codes which have been studied are linear-congruence codes; the Varshamov-Tenengol’ts codes , the Levenshtein codes , the Helberg codes , the Le-Nguyen codes , the construction C of Hagiwara  (for some parameters), the consecutively systematic encodable codes and the ternary integer codes in  fall into this category (Table).

Examples of linear-congruence codes
Linear-congruence code q $(a_1, \dotsc, a_n)$ m Constraints
Varshamov-Tenengol’ts code 2 $( 1, \dotsc, n)$ n + 1
Levenshtein code 2 $( 1, \dotsc, n)$ m m ≥ n + 1
Helberg code 2 $(v_1, \dotsc, v_n)$ vn + 1 s ∈ ℤ > 0
Le-Nguyen code q $(w_1, \dotsc, w_n)$ m m ≥ wn + 1, s ∈ ℤ > 0
Construction C 2 $(c_1, \dotsc, c_n)$ n $b \not\equiv 0, n(n+1)/2 \pmod n$
Consecutively systematic encodable codes 2 $(b_1, \dotsc, b_n)$ 2s + 1 b = 0, s ∈ ℤ > 0, 0 < n − s < 2s − 1
Ternary integer code 3 $(t_1, \dotsc, t_n)$ 2n + 1 − 1

The following problem concerning the size of a linear-congruence code—the number of solutions for a linear congruence equation [eq: ax = b]—is posed by Bibak and Milenkovic.

Problem

Give an explicit formula for the size of a linear-congruence code.

Finding an explicit formula would be a first step toward understanding the asymptotic behavior of the size of a linear-congruence code. Bibak and Milenkovic provide a solution to the problem for the binary case. In this article, we provide a complete solution to the problem with a simple proof, which improves the argument of Bibak and Milenkovic. Actually, what we will show is how the Hamming weights of the solutions for a linear congruence equation distribute. This immediately gives an expression of the size of a linear-congruence code involving exponential sums—Weyl sums of degree one.

To state the main theorem we need notation which will be standard.

Definition

For a code C ⊆ ℤqn, we define a polynomial WC(z) by $$W_C(z) = \sum_{x \in C} z^{wt(x)} = \sum_{i=0}^n A_i(C) z^i,$$ where $wt(x)$ denotes the Hamming weight and $$A_i(C) ≔ |{ x \in C : wt(x) = i }\rvert \qquad (0 \leq i \leq n).$$ The polynomial WC(z) is said to be the (non-homogeneous) weight enumerator of the code C.

Following custom due to Vinogradov in additive number theory, e(α) denotes $e^{2\pi\alpha\sqrt{-1}}$ for α ∈ ℝ. Now we are in position to state our main theorem.

Theorem

Let $a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$ and b ∈ ℤ. Then the weight enumerator WC(z) of the linear-congruence code $$\label{eq: LCC} C = { x \in \mathbb{Z}_q^n : a\cdot x \equiv b \pmod m }$$ is given by $$W_C(z) = \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \prod_{i=1}^n\left(1 + ze\left(\frac{ja_i}{m}\right) + \dotsb + ze\left(\frac{ja_i(q-1)}{m}\right)\right).$$

With the same notation as above, the size of the code C is given by $$\lvert C\rvert = \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \prod_{i=1}^n\left(1 + e\left(\frac{ja_i}{m}\right) + \dotsb + e\left(\frac{ja_i(q-1)}{m}\right)\right).$$

Proof of Theorem

The only lemma we need to prove the main theorem is the following trivial one.

$$\frac{1}{m}\sum_{j=1}^m e\left(\frac{jb}{m}\right) = \begin{cases} 1 & \mathrm{if } \ b \equiv 0 \pmod m \\ 0 & \mathrm{if } \ b \not\equiv 0 \pmod m . \end{cases}$$

The proof is straightforward: \begin{aligned} &\frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \prod_{i=1}^n\left(1 + ze\left(\frac{ja_i}{m}\right) + \dotsb + ze\left(\frac{ja_i(q-1)}{m}\right)\right) \\ &\qquad= \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \prod_{i=1}^n \sum_{x_i \in \mathbb{Z}_q} z^{wt(x_i)}e\left(\frac{ja_ix_i}{m}\right) \\ &\qquad= \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \sum_{(x_1, \dotsc, x_n) \in \mathbb{Z}_q^n} \prod_{i=1}^n z^{wt(x_i)}e\left(\frac{ja_i x_i}{m}\right) \\ &\qquad= \frac{1}{m}\sum_{j=1}^m e\left(-\frac{jb}{m}\right) \sum_{x \in \mathbb{Z}_q^n} z^{wt(x)}e\left(\frac{ja\cdot x}{m}\right) \\ &\qquad= \sum_{x \in \mathbb{Z}_q^n} \left(\frac{1}{m}\sum_{j=1}^m e\left(\frac{j(a\cdot x - b)}{m}\right) \right) z^{wt(x)} \\ &\qquad= \sum_{x \in C}z^{wt(x)} \qquad (\text{By Lemma.}) \\ &\qquad= W_C(z). \end{aligned}

Remark

The original proof by Bibak and Milenkovic  for the binary case uses a theorem of Lehmer , which states a linear congruence equation $$a\cdot x \equiv b \pmod m$$ defined by $a = (a_1, \dotsc, a_n) \in \mathbb{Z}^n$ and b ∈ ℤ has a solution x ∈ ℤmn if and only if $\gcd(a_1, \dotsc, a_n, m)$ divides b. Consequently, their result is stated depending on whether $\gcd(a_1, \dotsc, a_n, m)$ divides b or not. By contrast, our result does not refer to $\gcd(a_1, \dotsc, a_n, m)$ because our proof does not rely on the Lehmer theorem.

Acknowledgments

The author thanks Professor Manabu Hagiwara for drawing the author’s attention to the work of Bibak and Milenkovic and his invaluable help during the preparation of this article. This work is partially supported by KAKENHI(B) 18H01435, 16K12391 and 16K06336.

References

K. Bibak and O. Milenkovic, Weight enumerators of some classes of deletion correcting codes, IEEE ISIT (2018) 431–435, doi:10.1109/ISIT.2018.8437121.

M. Hagiwara, On ordered syndromes for multi insertion/deletion error-correcting codes, IEEE ISIT (2016) 625–629, doi:10.1109/ISIT.2016.7541374.

Perfect codes for single balanced adjacent deletions, IEEE ISIT (2017) 1938–1942, doi:10.1109/ISIT.2017.8006867.

A. S. J. Helberg and H. C. Ferreira, On multiple insertion/deletion correcting codes, IEEE Trans. Inf. Theory 48 (2002) 305–308, doi:10.1109/18.971760. MR 1872185 Zbl 1059.94040

T. A. Le and H. D. Nguyen, New multiple insertion/deletion correcting codes for non-binary alphabets, IEEE Trans. Inform. Theory 62 (2016), 2682–2693, doi:10.1109/TIT.2016.2541139. MR 3493869 Zbl 1359.94714

D. N. Lehmer, Certain theorems in the theory of quadratic residues, Amer. Math. Monthly 20 (1913) 151–157, doi:10.2307/2972413. MR 1517830 Zbl 44.0248.09

V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Dokl. 10 (1966) 707–710. MR 189928 Zbl 0149.15905

R. R. Varshamov and G. M. Tenengol’ts, Code correcting single asymmetric errors, Avtomat. i Telemeh. 26 (1965) 288–292. MR 172738