Python, Программирование

Восстановление информации, подверженной шумовому воздействию, с помощью кода РИДА–МАЛЛЕРА

Время прочтения: 4 мин.

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

А что, если я вам расскажу, что кодировка и декодировка используется для отправки информации на дальние расстояния. Звучит тоже немного странно, но предлагаю разобраться в этой теме поподробнее.

Когда люди только начали запускать различных дронов на дальние расстояния в Космос — не было возможности возвращать их обратно на Землю для получения и изучения добытой информации. Как говорится — «Это экономически невыгодно». Поэтому информацию, полученную с помощью дронов, решили отправлять по радиосвязи. Но первый такой опыт тоже был неудачным. Причина — отправленная информация подвергалась шумовому воздействию (например: фотографии выглядели совсем неинформативно).

Кажется, данную проблему решить невозможно, однако, это ошибочное заблуждение. Решением будет использование кода Рида-Маллера. Основная суть метода заключается в переведении отправленной информации в двоичную систему, потом умножение на порождающую матрицу, что в свою очередь увеличивает количество битов, выделенное на хранение одного символа. И в конечном итоге — данные, подверженные шумовому наложению, можно раскодировать с помощью голосования после умножения на проверочную матрицу. Этот подход также называется методом мажоритарного декодирования.

В этой статье я хочу показать применение этого алгоритма для декодирования обычных текстовых сообщений. Первым делом нужно определить какой алфавит будет использоваться. В моем случае он выглядит так:

#Алфавит
alph = 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЭЮЯабвгдеёжзийклмнопрстуфхцчшщъыьэюя0123456789.,!?;:№\'"(){}[]\\|/=+-*%^&$#@<>–—‘_`~«» '

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

#Словарь буква: позиция буквы в битовом виде
d1 = {a: [int(i) for i in f'{alph.index(a):07b}'] for a in alph}

С помощью данной конструкции мы записываем наш словарь в виде ключа. Где ключ — это символ, а соответствующий ему код записан в двоичной системе счисления. Пример можете увидеть на картинке ниже.

Теперь нужно объявить порождающую матрицу, она выглядит следующим образом:

#Порождающая матрица
gm = np.array([
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1],
[0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],
[0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],
])

В итоге — для увеличения длины выделенных битов на один символ нам нужно каждый ключ из нашего алфавита умножить на порождающую матрицу. В итоге получается уникальная последовательность символов с длинной 64.

Следующим шагом я реализовала функцию наложения шумов и назвала её — noise. В рандомном месте по длине закодированного символа меняем 1 на 0 и наоборот.

#Функция помех
def noise(arr,max_errors):
    d=list(arr)
    for i in range(max_errors):
        pos = random.choice(range(63))
        d[pos] = (1+d[pos]) % 2
    return d

Проверочная матрица является прототипом проверочных уравнений, для её создания можно использовать цикл, количество шагов равно необходимому количеству нужных проверочных уравнений. Функцию проверки (умножение на проверочную матрицу) я назвала sistem, так как практическим смыслом является решение системы уравнений.

# функция для решения систем уравнений
def sistem(с2,e_noisy):
    c2 = np.array([np.zeros(32, int) for i in range(6)])
    
    # создание матрици коэффициентов для проверочных уравнений
    for i in range(len(c1)):
        k = 0
        for j in range(len(c1[i])-1):
            if c1[i][j] != c1[i][j+1]:
                k = k+1
                c2[i][j+1] = k
            else:
                c2[i][j+1] = k
    for i in range(len(c2)):
        for j in range(len(c2[i])):
            c3[i][j] = (e_noisy[j+2**(5-i)*c2[i][j]] +
                        e_noisy[j+2**(5-i)*c2[i][j]+2**(5-i)]) % 2
    return c3

Осталось применить метод мажоритарного декодирования, для которого функция будет выглядеть так:

# функция голосования
def golos(c3):
    v = []
    for i in range(len(c3)):
        n0 = 0
        n1 = 0
        for j in range(len(c3[i])):
            if c3[i][j] == 0:
                n0 = n0+1
            else:
                n1 = n1+1
        if n0 > n1:
            v.append(0)
        else:
            v.append(1)
    return v

После выполнения этого шага нам возвращается «нормальная» кодировка символа, которую мы может декодировать в букву нашего алфавита.

#Функция декодирования для символа
def decode(s):
    return list(d1.keys())[list(d1.values()).index(s)]

Если показывать результат в обычном выводе в консольке, то это будет выглядеть очень скучно, поэтому я реализовала использование всех этих функции в программе с графическим интерфейсом с помощью библиотеки wx.

На первом примере программа успешно декодировала текст без помех, а на втором: количество ошибок — 6 и декодирование тоже прошло успешным образом.

Для более подробного изучения этого алгоритма советую почитать статью И. В. Агафонова «КОДЫ РИДА–МАЛЛЕРА: ПРИМЕРЫ ИСПРАВЛЕНИЯ ОШИБОК». Ну, а если хотите увидеть подробный разбор создания приложения с графическим интерфейсом на Python, то оставляй свой комментарий с пожеланиями.

Советуем почитать