Weight Enumerators for Number-Theoretic Codes
and Cardinalities of Tenengolts’ Non-binary Codes
Takayuki Nozaki
Yamaguchi University(This work supported by Inamori Research Grants)

ISIT2020

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

1 / 25

BackgroundError correcting codes are evaluated byError correcting capability(e.g., Decoding error rate, the number of correctable errors)
Code rate
Once error correcting capability is fixed, we should design a code withlarge rate.
[Definition] Rate of r-ary code[[r]] := {0, 1, 2, . . . , r − 1}C ⊂ [[r]]n : r-ary code of length n|C| : cardinality of the code (or number of codewords)
logr |C|(Rate) :=nThe rate is derived from the cardinality of the code.
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

2 / 25

Derivation of Cardinality
Linear Codes
Defined by the parity check matrix H
C := {x ∈ Fnr | HxT = 0T }Most of error correcting codes are linear codes
Cardinality is easily derived from code length n and rank of H
|C| = rn−rank(H)Number Theoretic Codes
Defined by one or more congruences ρi (x) ≡ ai (mod mi )ρi : [[r]]n → Z
C := {x ∈ [[r]]n | ρ1 (x) ≡ a1

(mod m1 ), ρ2 (x) ≡ a2

(mod m2 ), . . . }Most of deletion correcting codes are number theoretic codes
Derivation of cardinality is not easy problem|C| =?
How to derive the cardinalities of number theoretic codes?
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

3 / 25

Example: Cardinality of Binary VT CodeBinary VT Code [Varshamov-Teneholtz1965]
BVTa (n) := {x = x1 x2 · · · xn ∈ {0, 1}n |∑ni=1 ixi ≡ a(mod n + 1)}

a ∈ {0, 1, . . . , n}Single insertion/deletion correcting code [Levenshtein1966]
n=3
BVT0 (3) = {000, 101},

n=4
BVT0 (4) = {0000, 1001, 0110, 1111},

BVT1 (3) = {100, 011},

BVT1 (4) = {1000, 0101, 1110},

BVT2 (3) = {010, 111},

BVT2 (4) = {0100, 1101, 0011},

BVT3 (3) = {110, 001}

BVT3 (4) = {1100, 0010, 1011},BVT4 (4) = {1010, 0001, 0111},

Cardinality depends on not only code length n but also parameter a.
Which parameter a achieves the maximum cardinality (i.e., rate)?
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

4 / 25

Cardinality of Binary VT Code[Ginzburg1967], [Stanley-Yoder1972]|BVTa (n)| =12(n + 1)∑

cd (a)2(n+1)/dd|(n+1),d:odd∑

d|(n+1),d:odd expresses summation over odd d that divides (n + 1)

cd (a) : Ramanujan’s sum
cd (a) = ϕ(d)dµ( gcd(a,d))
dϕ( gcd(a,d))

gcd(a, b): Greatest common divisor of a and bµ(n): Möbius function
ϕ(n): Euler’s totient function

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

5 / 25

Cardinality of Binary VT Code[Ginzburg1967], [Stanley-Yoder1972]|BVTa (n)| =12(n + 1)∑

cd (a)2(n+1)/dd|(n+1),d:odd

Outline of Derivation:
1

Calculating Hamming weight enumeratorn∑∑
H(BVTa (n); z) :=z wtH (x) =Ai z ix∈BVTa (n)i=0wtH (x): Hamming weight (the number of non-zero entries) of x
Ai : the number of codewords of weight i in BVTa (n)2Deriving cardinality by the following identity∑H(BVTa (n); 1) =1 = |BVTa (n)|x∈BVTa (n)T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

5 / 25

Binary Linear Congruence Code
Binary Linear Congruence (BLC) Code [Bibak-Milenkovic2018]
A general class of number-theoretic code
Binary code defined by a linear congruence∑BLCa (n, m, h) := {x ∈ {0, 1}n | ni=1 hi xi ≡ a (mod m)}h = (h1 , h2 , . . . , hn ) ∈ Nnbinary

linear congruence[Bibak-Milenkovic2018] derived weight enumerate of BLC CodeCodes included in BLC code
VT code {x ∈ {0, 1}n |∑ni=1 ixi ≡ a (mod n + 1)}∑Levenshtein code {x ∈ {0, 1}n | ni=1 ixi ≡ a (mod m)}

Helberg code
Odd coeﬃcient code {x ∈ {0, 1}n |T. Nozaki (Yamaguchi Univ.)∑ni=1 (2i − 1)xi ≡ b (mod R)}

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

6 / 25

Binary Linear Congruence Code
Binary Linear Congruence (BLC) Code [Bibak-Milenkovic2018]
A general class of number-theoretic code
Binary code defined by a linear congruence∑BLCa (n, m, h) := {x ∈ {0, 1}n | ni=1 hi xi ≡ a (mod m)}h = (h1 , h2 , . . . , hn ) ∈ Nn

binarylinear congruence

However, BLC code does not contain several number-theoretic codes.
(Example) Tenengolts’ Non-binary code [Tenengolts1984]
Non-binary code defined by two non-linear/linear congruences
Ta,b (n, r) = {x ∈ [[r]]n | γ(x) ≡ a (mod n), σ(x) ≡ b (mod r)}
r-ary
non-linear cong.
linear cong.
∑{γ(x) := n−1iI{x>x}ii+1i=1
1 P is true
I{P } =(non-linear mapping)0 P is false∑
σ(x) := ni=1 xi
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

6 / 25

Purpose and Outline of This Talk
Purpose of this research
Deriving the cardinality of the Tenengolts’ non-binary code
1Define SC code
More general class of number
theoretic code
Include Tenengolts’ non-binary code

T. Nozaki (Yamaguchi Univ.)

2

Weight enumerator for SC code3

Weight enumerator for Tenengolts’
non-binary code4

Cardinality for Tenengolts’ non-binarycode

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

7 / 25

Non-binary Simultaneous Congruences CodeNon-binary simultaneous congruences (SC) code
For all 1 ≤ i ≤ s, ρi : [[r]]n → Zr-arys non-linear congruences

Cρ,a,m (n, r) = {x ∈ [[r]]n | ρ1 (x) ≡ a1

(mod m1 ),ρ2 (x) ≡ a2..
.

(mod m2 ),ρs (x) ≡ as(mod ms )}Comparison with BLC code

BLC CodeSC Codedefined bybinary single
r-ary
multiplelinearnon-linear

congruencecongruences

Note: SC code is a generalization of BLC code
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

8 / 25

Codes included in SC codeCρ,a,m (n, r) = {x ∈ [[r]]n | ρ1 (x) ≡ a1

(mod m1 ),ρ2 (x) ≡ a2..
.

(mod m2 ),ρs (x) ≡ as(mod ms )}Codes included in SC code
s=2ShiftedVT code
∑nixi ≡ a1 (mod R),
i=1∑ni=1 xi ≡ a2 (mod 2)

Tenengolts’
non-binary code∑n−1i=1 iI{xi > xi+1 } ≡ a1 (mod n),∑ni=1 xi ≡ a2 (mod r)

s=3
Non-binary
Shifted VT code∑n−1i=1 iI{xi > xi+1 } ≡ a1 (mod R), ∑∑n−1ni=1 I{xi > xi+1 } ≡ a2 (mod 2),i=1 xi ≡ a3 (mod r)
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

9 / 25Extended Weight Enumerator[Definition] Extended weight enumeratorz = (z1 , z2 , . . . , zs )w = (w0 , w1 , . . . , wr−1 )τj (x) := |{i | xi = j}| : number of entries which equals to j in x∑

Wρ (Cρ,a,m (n, r); z, w) =r−1s∏ τj (x)∏ρ (x)
zi iwjx∈Cρ,a,m (n,r) i=1

j=0[Example] Extended weight enumerator for Tenengolts’ NB code
Ta1 ,a2 (n, r) = {x ∈ [[r]]n | γ(x) ≡ a1
Wγ,σ (Ta1 ,a2 (n, r); (z1 , z2 ), w) =(mod n), σ(x) ≡ a2∑x∈Ta1 ,a2 (n,r)
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

γ(x) σ(x)z2z1(mod r)}r−1∏τ (x)

wj j

j=0ISIT2020

10 / 25

Example of Extended Weight Enumerator[Example] Tenengolts’ non-binary code (n = 3, r = 3)
T0,0 (3, 3) = {000, 012, 111, 210, 222}
x

γ(x)

σ(x)

τ0 (x)

τ1 (x)

τ2 (x)

000012
111
210
222

000
300
333
63
10
10013
100
1013

τj (x)
γ(x) σ(x) ∏2z2j=0 wj
w03
3z 2 w0 w1 w2z23 w13z13 z23 w0 w1 w2z26 w23

z1∑Wγ,σ (T0,0 (3, 3); (z1 , z2 ), w)?

= w03 + z23 w0 w1 w2 + z23 w13 + z13 z23 w0 w1 w2 + z26 w23

γ(x) :=n−1∑iI{xi > xi+1 },σ(x) :=

i=1
T. Nozaki (Yamaguchi Univ.)

n∑

xi

i=1
Cardinalities of Tenengolts’ NB-Codes

ISIT2020

11 / 25

Property of Extended Weight Enumerator
Extended weight enumerator is a generalization of Hamming weightenumerator
H(Cρ,a,m (n, r); w) = Wρ (Cρ,a,m (n, r); 1, w∗ )1 := (1, 1, . . . , 1), w∗ := (1, w, w, . . . , w)
∑Wρ (Cρ,a,m (n, r); z, w) =x∈Cρ,a,m (n,r)∑H(Cρ,a,m (n, r); w) =( s)()r−1
∏ ρ (x)∏ τj (x)τ0 (x)
izi
w0wj
i=1

j=1

wwtH (x)x∈Cρ,a,m (n,r)

Note: wtH (x) =∑r−1

T. Nozaki (Yamaguchi Univ.)

j=1 τj (x).

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

12 / 25

Extended weight enumerator for SC code
Theorem 1Wρ (Cρ,a,m (n, r); z, w)()
m1 ∑m2mss∑∑∏ai ki1n=···Wρ ([[r]] ; ze(k/m), w)e −,mimi
k1 =1 k2 =1

i=1

ks =1

where ze(k/m) := (z1 e(k1 /m1 ), z2 e(k2 /m2 ), . . . , zt e(ks /ms )).
Remark: Weight enumerator for SC code Wρ (Cρ,a,m (n, r); z, w) is
derived from Weight enumerator for whole space Wρ ([[r]]n ; z, w)i=√e(2/6)−1jje( m) = exp[2πi m](points of unit circle on complexplain)

T. Nozaki (Yamaguchi Univ.)e(3/6)e(4/6)

Cardinalities of Tenengolts’ NB-Codese(1/6)e(0/6)e(5/6)
ISIT2020

13 / 25

Proof of Theorem 1
Lemmas to derive Theorem 1
1

Condition of summation is written by an indicator function:∑∑f (x) =f (x)I[x ∈ C]
x∈C⊆[[r]]n2i∈[[r]]n

If C := {x | ∀i ∈ {1, 2, . . . , s} ρi (x) ≡ ai (mod mi )}, thenI[x ∈ C] =s∏I[ρi (x) ≡ ai(mod mi )]i=1
3

I[A ≡ B(mod m)] = I[(A − B) ≡ 0 (mod m)]()m(A − B)j1 ∑e=mm
j=1

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

14 / 25

Wρ (Cρ,a,m (n, r); z, w)
s
∑
∏
ρ (x)
=wτ (x)zi ii=1

x∈Cρ,a,m (n,r)(1)=∑wτ (x) I[x ∈ Cρ,a,m (n, r)]x∈[[r]]n(2)

=∑w

τ (x)

( s∏

x∈[[r]]ns∏
ρ (x)
zi i
i=1

I{ρi (x) ≡ ai)( s)∏ ρ (x)i(mod mi )}zi

i=1i=1( s)()) ( ∏mis
∏ 1 ∑(ρi (x) − ai )ki(3) ∑ρi (x)
τ (x)
=w
e
zi
mi
mi
i=1i=1ki =1x∈[[r]]n( s m)() ()i∑∏∑
1−ai ki
ρi (x)ki
ρi (x)
τ (x)
=w
e
e
zi
mi
mi
mi
i=1 ki =1x∈[[r]]n)( s ( ( )))( sm1msρi (x)∑∏∑∑∏ 1 ( −ai ki )ki=ewτ (x)zi e···mm
miii
ni=1k1 =1
ks =1 i=1x∈[[r]])( sm1ms∑∑∏ 1 ( −ai ki )=···eWρ ([[r]]n ; ze(k/m), w)
mmiii=1

k1 =1
ks =1
T. Nozaki(YamaguchiUniv.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

15 / 25

Cardinality of Tenengolts’ non-binary code
Theorem 3
For any a1 ∈ [[n]], a2 ∈ [[r]], the cardinality of Tenengolts’ non-binary codeisn
1 ∑|Ta1 ,a2 (n, r)| =cd (a1 )r d gcd(r, d)I{d | n}I{gcd(r, d) | a2 }.
nr+d∈Z

Corollary 1
Let n, r ∈ Z+ , a1 ∈ [[n]] and a2 ∈ [[r]]. For any n, r, a1 , a2 , the following
holds|T0,0 (n, r)| ≥ |Ta1 ,a2 (n, r)|Note: cd (0) ≥ cd (a) for all a ∈ Z.

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

16 / 25

Example:
Ta1 ,a2 (3, 3) = {x ∈ [[3]]3 | γ(x) ≡ a1

a1 = 0a1 = 1a1 = 2a2 = 0{000, 012, 111,210, 222}
{102, 201}{021, 120}

From Theorem 3,|Ta1 ,a2 (3, 3)| = 19

∑

d|3 3

(mod 3), σ(x) ≡ a2(mod 3)}

a2 = 1a2 = 2{001, 022, 112}{002, 011, 122}

{100, 202, 211}
{010, 121, 220}

{101, 200, 212}
{020, 110, 221}3/d c (a ) gcd(3, d)I{gcd(3, d) | a }2d 1= 3c1 (a1 ) + I{3 | a2 }c3 (a1 )Note that c1 (0) = 1, c3 (0) = 2, c3 (1) = c3 (2) = −1. We get5, if a1 = 0 and a2 = 0,
|Ta1 ,a2 (3, 3)| = 2, if a1 = 1, 2 and a2 = 0,
3, if a2 = 1, 2.
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

17 / 25

Derivation of the cardinality of Tenengolts’ non-binary code
Ta1 ,a2 (n, r) = {x ∈ [[r]]n | γ(x) ≡ a1
1(mod n), σ(x) ≡ a2(mod r)}

Deriving the extended weight enumerator for [[r]]nWγ,σ ([[r]]n ; (q, z), w)

2

Calculating the Hamming weight enumerator for Ta1 ,a2 (n, r)
H(Ta1 ,a2 (n, r); w)= Wγ,σ (Ta1 ,a2 (n, r); (1, 1), w∗ )n ∑r) ()∑1 (=Wγ,σ ([[r]]n ; (e( kn1 ), e( kr2 )), w∗ ) e − a1nk1 e − a2rk2nr
k1 =1 k2 =13

Deriving the cardinality|Ta1 ,a2 (n, r)| = H(Ta1 ,a2 (n, r); 1)

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

18 / 25

Extended Weight Enumerator of Whole Space (Notation)
Let τj (x) be number of symbol j in sequence x ∈ [[r]]n , i.e.,τj (x) := |{i ∈ {1, 2, . . . , n} | xi = j}|(Example) τ0 (1020) = 2, τ1 (1020) = 1, τ2 (1020) = 1
The type of sequence x is(τ0 (x), τ1 (x), . . . , τr−1 (x))(Example) Type of sequence 1020 is (2, 1, 1).
Denote the set of sequences with type t, by S(t) i.e.,S(t) = {x : (τ0 (x), τ1 (x), . . . , τr−1 (x)) = t}(Example) S(2, 1, 1) ={0012, 0021, 0102, 0120, 0201, 0210, 1002, 1020, 1200, 2001, 2010, 2100}
T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

19 / 25

Extended Weight Enumerator of Whole SpaceLemma 2 [Ch.VI, MacMahon1915]
∑q

γ(x)

x∈S(t)∏n[ ]jn
j=1 (q − 1):= ∏r−1 ∏ti=kt qi=0
k=1 (q − 1)

Tn := {(t0 , t1 , . . . , tr−1 ) ∈ Z≥0 :∑r−1

i=0 ti = n},Lemma 5
Wγ,σ ([[r]] ; (q, z), w) =n∑ [n] r−1∏t∈Tn

T. Nozaki (Yamaguchi Univ.)t q

Cardinalities of Tenengolts’ NB-Codes

twjj z jtj

j=0ISIT2020

20 / 25

Proof: From Lemma 2Wγ,σ (S(t); ⟨q, z⟩, w) =∑qγ(x)x∈S(t)Since [[r]]n =∪∏t
wjj z jtj =j∈[[r]][ ] ∏nt
wjj z jtj .
t qj∈[[r]]′′t∈Tn S(t) and S(t) ∩ S(t ) = ∅ for t ̸= t ,Wγ,σ ([[r]]n ; (q, z), w) =∑Wγ,σ (S(t); (q, z), w)t∈Tn

Combining theseWγ,σ ([[r]]n ; (q, z), w) =∑Wγ,σ (S(t); (q, z), w)t∈Tn=∑ [n ] ∏t∈TnT. Nozaki (Yamaguchi Univ.)t qt

wjj z jtjj∈[[r]]Cardinalities of Tenengolts’ NB-Codes

ISIT2020

21 / 25Derivation of the cardinality of Tenengolts’ non-binary code1

Deriving the extended weight enumerator for [[r]]nWγ,σ ([[r]] ; (q, z), w) =n∑ [n] r−1∏t∈Tn,r2t qt

wjj z jtj

j=0

Calculating the Hamming weight enumerator for Ta1 ,a2 (n, r)
H(Ta1 ,a2 (n, r); w)n ∑r) ()
∑1 (=Wγ,σ ([[r]]n ; (e( kn1 ), e( kr2 )), w∗ ) e − a1nk1 e − a2rk2
nr
k1 =1 k2 =1

3

Deriving the cardinality|Ta1 ,a2 (n, r)| = H(Ta1 ,a2 (n, r); 1)

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

22 / 25

Hamming weight enumerator for Tenengolts’ NB-code
Lemma 6
For any k1 ∈ [[n]], k2 ∈ [[r]], we get
Wγ,σ ([[r]]n ; (e( kn1 ), z), w) =(∑ni gcd(n,k1 )i∈[[r]] (wi z ))gcd(n,k1 )Proof: The following holds (generalization of [Hagiwara-Kong2019]):[∑](∑) ∏j∈[[r]] ti /dj∈[[r]] tilim=
I{d | ti },tq→e(1/d)
t/dqi∈[[r]]nFor a fixed k1 , define d := gcd(n,k. Then, e(k1 /n) is a primitive d-th root1)of unity. Lemma 5 gives
Wγ,σ ([[r]]n ; (e( kn1 ), z), w) =∑ (n/d) ∏t

wjj z jtj I{d | tj }t/dt∈Tnj∈[[r]](∑)n/d∑ (n/d) ∏′d id=(wj z j )dtj =,′i∈[[r]] wi zt′t ∈Tn/dT. Nozaki (Yamaguchi Univ.)

j∈[[r]]

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

23 / 25

Hamming weight enumerator for Tenengolts’ NB-code
Theorem 2: Hamming weight enumerator
H(Ta1 ,a2 (n, r); w) =1nr∑∑

cd (a1 )ce (a2 )d∈Z+ ,d|n e∈Z+ ,e|r{}nddd
× 1 − w + rw I{e | d},Outline of Proof: Using the following properties
H(Ta1 ,a2 (n, r); w) =n ∑r∑

Wγ,σ ([[r]]n ; (e( kn1 ), e( kr2 )), w∗ )k1 =1 k2 =1

×1 ( a1 k1 ) ( a2 k2 )e − n e − rnr)(n,k1 )(⟨ ( ) ( )⟩) (nnnk2Wγ,σ [[r]]n ; e kn1 , e kr2 , w∗ = 1 − w (n,k1 ) + rw (n,k1 ) I{r | (n,k}.
1))(∑ajcd (a) =ed
j∈[[1,d]],(j,d)=1

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

24 / 25

Conclusion

We derived a formula of extended weight enumerator of the SC code
We provided the Hamming weight enumerators of the Tenengolts’
non-binary codes
We gave the cardinalities of the Tenengolts’ non-binary codes

T. Nozaki (Yamaguchi Univ.)

Cardinalities of Tenengolts’ NB-Codes

ISIT2020

25 / 25