Генерируйте двоичные строки, которые по крайней мере на расстоянии d Hamming, используя ECC - PullRequest
Новая
       44

Генерируйте двоичные строки, которые по крайней мере на расстоянии d Hamming, используя ECC

0 голосов
/ 15 октября 2018

Я хочу сгенерировать двоичные строки длиной n = 128 со свойством, что любая пара таких строк находится по крайней мере на расстоянии d = 10 Хэмминга.

Для этого я пытаюсь использовать код исправления ошибок (ECC) с минимальным расстоянием d = 10.Тем не менее, я не могу найти ecc, который имеет кодовые слова длиной 128 бит.Если длина кодового слова (n) и d немного меньше / больше 128 и 10, это все еще работает для меня.

Есть ли ecc с этими (похожими) свойствами?Есть ли в Python такая реализация?

1 Ответ

0 голосов
/ 16 октября 2018

Коды Рида-Мюллера RM (3,7) имеют:

  • размер блока 128 бит
  • минимальное расстояние 16
  • размер сообщенияиз 64 битов

Сначала создайте базу следующим образом: 

def popcnt(x):
    return bin(x).count("1")

basis = []
by_ones = list(range(128))
by_ones.sort(key=popcnt)
for i in by_ones:
    count = popcnt(i)
    if count > 3:
        break
    if count <= 1:
        basis.append(((1 << 128) - 1) // ((1 << i) | 1))
    else:
        p = ((1 << 128) - 1)
        for b in [basis[k + 1] for k in range(7) if ((i >> k) & 1) != 0]:
            p = p & b
        basis.append(p)

Затем вы можете использовать любую их линейную комбинацию, которая создается XORing подмножествами строк базы,например: 

def encode(x, basis):
    # requires x < (1 << 64)
    r = 0
    for i in range(len(basis)):
        if ((x >> i) & 1) != 0:
            r = r ^ basis[i]
    return r

В какой-то другой реализации я обнаружил, что это было сделано, взяв точечные произведения со столбцами базисной матрицы, а затем уменьшив их по модулю 2. Я не знаю, почему они это делают, кажется, оченьпроще сделать это напрямую, суммируя подмножество строк.

...