OFFSET
3,1
COMMENTS
The maximum number of codewords for different N in Helberg code for two deletion binary Helberg code.
LINKS
K. A. S. Abdel-Ghaffar, F. Paluncic, H. C. Ferreira and W. A. Clarke, On Helberg's Generalization of the Levenshtein Code for Multiple Deletion/Insertion Error Correction, IEEE Transactions on Information Theory, vol. 58, no. 3, pp. 1804-1808, March 2012, doi: 10.1109/TIT.2011.2174961. See also on ResearchGate.
EXAMPLE
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.
The same formula is used to calculate 'a' and then the maximum number of codewords for different values of N.
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.
PROG
(Python)
import numpy as np
import sys
def String_generate(n, k, x, final_list):
if n == 0:
final_list.append(x[:])
else:
for j in range(0, k):
x.append(j)
String_generate(n-1, k, x, final_list)
x.pop()
return x
def Vi_generate(n, s, v):
for i in range(0, n):
for j in range(1, s+1):
v[i] += v[i-j] if (i-j >= 0) else 0
def find_M(v, s, n):
m = 1
for i in range(1, s+1):
m += v[n-i]
return m
def func(num, v, m, n, ans):
sum = 0
for i in range(0, n):
sum += v[i]*num[i]
sum = sum % m
if sum not in ans:
ans[sum] = []
ans[sum].append(num)
def a(n):
x = []
final_list = []
q = 2
s = 2
v = np.ones(n)
ans = {}
if s < n:
String_generate(n, q, x, final_list)
x = final_list
x = np.array(x)
Vi_generate(n, s, v)
m = find_M(v, s, n)
for i in x:
func(i, v, m, n, ans)
else:
ans[0] = []
return max(len(v) for v in ans.values())
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Devdeep Shetranjiwala and Manish Gupta, Oct 28 2023
STATUS
approved