login
Maximum number of codewords in a binary Herbert code of length n that corrects two deletions.
0

%I #41 Nov 08 2023 11:16:36

%S 2,2,2,3,4,5,6,8,9,11,15,18,22,30,35,43,57,69,88,114,142,177,227

%N Maximum number of codewords in a binary Herbert code of length n that corrects two deletions.

%C The maximum number of codewords for different N in Helberg code for two deletion binary Helberg code.

%H K. A. S. Abdel-Ghaffar, F. Paluncic, H. C. Ferreira and W. A. Clarke, <a href="https://doi.org/10.1109/TIT.2011.2174961">On Helberg's Generalization of the Levenshtein Code for Multiple Deletion/Insertion Error Correction</a>, IEEE Transactions on Information Theory, vol. 58, no. 3, pp. 1804-1808, March 2012, doi: 10.1109/TIT.2011.2174961. See also <a href="https://www.researchgate.net/publication/260541992_On_Helberg&#39;s_Generalization_of_the_Levenshtein_Code_for_Multiple_DeletionInsertion_Error_Correction">on ResearchGate</a>.

%e For N = 4, using the Helberg formula Equation 2 in the reference paper, we will get different values of 'a' for different codewords. Now, the maximum number of codewords for a particular 'a' will be 2 in this example.

%e The same formula is used to calculate 'a' and then the maximum number of codewords for different values of N.

%e Note: The first term will be obtained by applying the Helberg formula (Equation 2) with an offset of three. The first term will be calculated as a(3)=2.

%o (Python)

%o import numpy as np

%o import sys

%o def String_generate(n, k, x, final_list):

%o if n == 0:

%o final_list.append(x[:])

%o else:

%o for j in range(0, k):

%o x.append(j)

%o String_generate(n-1, k, x, final_list)

%o x.pop()

%o return x

%o def Vi_generate(n, s, v):

%o for i in range(0, n):

%o for j in range(1, s+1):

%o v[i] += v[i-j] if (i-j >= 0) else 0

%o def find_M(v, s, n):

%o m = 1

%o for i in range(1, s+1):

%o m += v[n-i]

%o return m

%o def func(num, v, m, n, ans):

%o sum = 0

%o for i in range(0, n):

%o sum += v[i]*num[i]

%o sum = sum % m

%o if sum not in ans:

%o ans[sum] = []

%o ans[sum].append(num)

%o def a(n):

%o x = []

%o final_list = []

%o q = 2

%o s = 2

%o v = np.ones(n)

%o ans = {}

%o if s < n:

%o String_generate(n, q, x, final_list)

%o x = final_list

%o x = np.array(x)

%o Vi_generate(n, s, v)

%o m = find_M(v, s, n)

%o for i in x:

%o func(i, v, m, n, ans)

%o else:

%o ans[0] = []

%o return max(len(v) for v in ans.values())

%K nonn,more

%O 3,1

%A _Devdeep Shetranjiwala_ and Manish Gupta, Oct 28 2023