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

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

В 1969 году, при помощи искусственных спутников Mariner 6 и Mariner 7, было получено около двухсот фотографий Марса. Каждая фотография состояла из 658 240 восьмибитных пикселей. Таким образом, для каждой фотографии требовалось около 5‑ти миллионов бит информации. Эти биты были кодированы кодом, исправляющим ошибки, и переданы со скоростью 16 200 бит в секунду на Землю, где они были успешно декодированы.

1. Постановка задачи

Была поставлена задача создать программную реализацию алгоритмов кодирования и декодирования двоичных кодов исправляющих ошибки: БЧХ-кодов и кодов Рида‑Маллера, а также программу для работы с кодами, предоставляющая возможности кодирования и декодирования информации.

Из семейства БЧХ-кодов был выбран БЧХ(5, 15, 7), где

5 – длина информационного слова;

15 – длина кодового слова;

7 – минимальное расстояние кода.

Из семейства кодов Рида-Маллера (RM) был выбран RM(2, 5), где

2 – порядок кода Рида-Маллера

5 – задает длину кодового слова, 2⁵=32.

Для написания программы была выбрана среда разработки Borland Delphi 6.

2. Реализация кодов

2.1. Общие сведения

Базовым классом всех кодов является TCode из модуля Code.pas. Сам же TCode является наследником TComponent. TComponent входит в состав стандартной библиотеки классов Delphi VCL. Благодаря наследованию TCode от TComponent, экземпляры класса TCode (и его наследники) можно сохранять в потоки, и, при необходимости, восстанавливать их из потоков (под потоком подразумевается класс TStream, также входящий в состав стандартных библиотек Delphi). Это используется программой Magic Coder при кодировании и декодировании файлов. Более подробно о Magic Coder будет рассказано далее.

2.2. БЧХ(5, 15, 7)

Порождающей матрицей данного кода является:

По построению код способен исправлять любые ошибки, вес которых не больше 3-х.

БЧХ-код выполнен в виде класса TBCHCode, который находится в модуле BCH.pas.

В целях повышения скорости, используется табличный способ кодирования и декодирования. Соответствующие таблицы заполняются методами TBCHCode.BuildEncodeTable и TBCHCode.BuildDecodeTable, которые вызываются в конструкторе класса. Таблица кодирования занимает

байта, а таблица декодирования –

байт.

2.3. Код Рида-Маллера

Код Рида-Маллера RM(r, m) имеет следующие характеристики:

длина информационного слова:
;
длина кодового слова:
;
минимальное расстояние:

Несмотря на постановку задачи, вместо реализации кода RM(2, 5) был создан универсальный класс TRMCode (RM.PAS). TRMCode позволяет работать с кодами Рида‑Маллера произвольных параметров. В конструкторе класса можно указать нужные параметры кода. Если этого не сделать, то будет создан код RM(2, 5).

Кодирование производится умножением информационного слова (вектора) на порождающую матрицу. Порождающая матрица создается методом BuildGeneratorMatrix, который вызывается при задании параметров кода.

Декодирование производится алгоритмом «мажорандного голосования». Для мажорандного голосования требуются характеристические векторы, они строятся методом BuildCharacterVectors, который, как и BuildGeneratorMatrix, вызывается при задании параметров кода.

3. Magic Coder

3.1. Руководство пользователя

Magic Coder – это тестовая программа для реализованных кодов: БЧХ и RM. Исходные коды всех ее модулей можно найти на веб‑страничке http://slava.fateback.com/work/ecc.

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

Нажав на кнопку «Дополнительно», вы откроете окно, в котором можно вводить информационное слово, а в ответ получать его кодированный вариант (кодовое слово). Повторное нажатие кнопки «Дополнительно» закрывает окно.

Рассмотрим меню программы.

3.1.1. Меню «Файл»

Оно состоит из следующих пунктов:

Кодировать
Декодировать
Выход

При выборе пункта «Кодировать», программа попросит указать файл, который вы хотите кодировать. Затем будет запрошено имя файла, в который программа запишет кодированный вариант исходного файла. По умолчанию, кодированные файлы имеют расширение «.enc». Кодирование производится кодом, который выбран в списке главного окна.

Для того чтобы декодировать файл, выберите пункт меню «Декодировать». Программа попросит указать кодированный файл, а также имя файла, в который будет записан декодированный вариант файла. Декодирование производится тем кодом, которым он был кодирован (информация о коде берется из специального заголовка в файле), независимо от того, какой код на данный момент выбран в главном окне.

Если же вы хотите завершить работу с программой, то выберите пункт «Выход».

3.1.2. Меню «Код»

Оно состоит из следующих пунктов:

Анализ кода
Демонстрация

Пункт «Анализ кода» при активации открывает окно, в котором производится анализ следующего рода: сколько ошибок и какого веса способен исправить код. Данный анализ позволяет определить поведение кода при ошибках в кодовых словах, исправление которых не заложено в него. Например, БЧХ(5, 15, 7) по построению способен исправить любые ошибки, вес которых не превышает 3-ех. Однако, после анализа становится видно, что он способен исправлять некоторые ошибки веса 4 и 5. Пару слов о том, как интерпретировать результаты. В колонке «Исправлено» выводится число пар {кодовое слово, вектор ошибки} таких, что код сумел правильно декодировать слово, полученное наложением вектора ошибки на кодовое слово (операция xor). В колонке «Не исправлено» – число остальных пар.

При выборе пункта «Демонстрация», программа попросит вас указать файл с изображением (bmp или jpg). После этого появится окно, в котором можно визуально сравнить разницу между передачей информации по зашумленному каналу без кодирования и с кодированием. В центре отображается оригинальное изображение, слева – изображение, переданное через канал, а справа – изображение, кодированное перед передачей, и декодированное после.

По умолчанию, шумов нет. Соответственно нет и разницы между выводимыми изображениями. Уровень шумов задается бегунком в верхней части окна. Под уровнем шумов понимается равномерно-распределенная вероятность ошибки при передаче одного бита информации. При установке минимального уровня, вероятность ошибки равна 0, а при установке максимального уровня – 1, что приводит к инвертированию всех переданных бит.

Изображение, не помещающееся в отведенном участке окна полностью, можно прокручивать мышью, предварительно зажав кнопку мыши на изображении.

3.2. Добавление новых кодов

Если вы хотите добавить поддержку нового кода, то вы должны сделать следующее:

«Файл» (стр. 1 из 4)

3. Magic Coder