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

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

Offset

3,1

Comments

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

Links

Table of n, a(n) for n=3..25.

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

Sequence in context: A258327 A102240 A026837 * A005855 A096748 A263659

Adjacent sequences: A366913 A366914 A366915 * A366917 A366918 A366919

Keyword

nonn,more

Author

Devdeep Shetranjiwala and Manish Gupta, Oct 28 2023

Status

approved