Программная реализация алгоритмов кодирования и декодирования для БЧХ-кодов и кодов Рида-Маллера

Федеральное агентство  по образованию

Государственное образовательное  учреждение  
высшего профессионального образования

Омский государственный  университет им. Ф.М. Достоевского

 

Математический факультет

Кафедра математической логики и логического программирования

 

 

 

 

 

Программная реализация алгоритмов кодирования и декодирования  для БЧХ-кодов и кодов Рида-Маллера

 

 

 

 

Аттестационная работа

студента группы ММ-102

Антонова В.И.

_______________ (подпись)

Научный руководитель

доцент,  кандидат ф.- м. наук

Ашаева Ю.М.

_______________ (подпись)

 

 

 

 

 

 

 

 

Омск - 2005

Содержание

 

 

 

ВВЕДЕНИЕ

С ростом использования электроники  и компьютеров, растет потребность в быстрой и надежной передаче информации по радио- и телефонным каналам связи, а также от одного устройства к другому. В любом канале связи присутствуют шумы – сигналы, которые могут искажать передаваемую по каналу информацию. С этими искажениями можно бороться, преобразуя передаваемую информацию при помощи кода, который будет обнаруживать, и исправлять ошибки. Так, например, в 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. Реализация кодов

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Magic Coder

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

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

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

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

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

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

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

1. Кодировать
2. Декодировать
3. Выход

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

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

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

2. Меню «Код»

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

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

 

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

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

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

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

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

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

• Добавить новый модуль к проекту MagicCoder.dpr.
• В полученном модуле создать наследника класса TCode, например, TMyCode.
• Перекрыть методы¹: 
  GetK 
  GetN 
  GetName 
  Encode 
  Decode
• При желании перекрыть методы: 
  GetD 
  GetDescription 
  GetFullName
• Добавить в модуль секции initialization и finalization следующего содержания: 
  initialization 
    RegisterCode(TMyCode) 
   
  finalization 
    UnRegisterCode(TMyCode)

Этого будет достаточно для того, чтобы добавить полную поддержку нового кода.

3. Описание модулей программы

Во всех модулях программы обработка  ошибок основана на механизме исключительных ситуаций (exceptions). Описание модулей программы выполнено в виде комментариев в стиле Delphi к объявлениям классов, их полей и методов; функций и констант.

1. Модуль «BitsUtils.pas»

{ В этом модуле находится реализация класса для работы

  с массивом бит, TBits }

unit BitsUtils;

 

interface

 

uses

  Math, SysUtils, Windows, SysConst;

 

{ Для хранения битов используется массив 32-битных целых.

  Т.е. для хранения от 1 до 32 бит будет использован один элемент массива, для хранения от 33 до 64 бит – 2 элемента и т.д. }

const

{ Число байт в элементе массива }

  BITSUNIT_SIZE = 4;

{ Число бит в элементе массива }

  BITSUNIT_BITS = BITSUNIT_SIZE * 8;

{ Маска элемента массива }

  BITSUNIT_MASK = $FFFFFFFF;

type

{ Указатель на элемент }

  PUnit = ^TUnit;

{ Тип элемента массива }

  TUnit = DWORD;

 

type

{ Бит }

  TBit = 0..1;

 

{ Исключение, которое генерируют большинство методов класса TBits }

  EBits = class(Exception);

 

{ Класс TBits }

  TBits = class(TObject)

  private

  { Число бит в массиве }

    FBitsCount: Integer;

  { Указатель на массив, в котором хранятся биты }

    FData: PUnit;

  { Размер массива в байтах }

    FDataSize: Integer;

  { Число элементов в массиве }

    FUnitsCount: Integer;

 

    procedure AllocMemory(ABitsCount: Integer);

      { На основе ABitsCount вычисляет значения FDataSize,

        FUnitsCount и выделяет память размера FDataSize переводя

        указатель FData на выделенный кусок }

 

    function GetBit(Index: Integer): TBit;

      { Возвращает значение бита по его индексу. При

        недопустимом индексе генерирует исключение EBits }

    procedure SetBit(Index: Integer; const Value: TBit);

      { Присваивает указанному биту заданное значение.

        При недопустимом индексе генерирует исключение EBits }

  public

    constructor Create(ABitsCount: Integer); overload;

    constructor Create(Src: TBits); overload;

      { Конструктор копирования }

    constructor Create(Src: String); overload;

      { Конструктор копирования }

 

    destructor Destroy; override;

 

  { Методы присваивания }

    function Assign(Src: TBits): TBits; overload;

    function Assign(S: String): TBits; overload;

      { Все символы отличные от ‘0’ воспринимаются как ‘1’ }

 

    function Equals(Bits: TBits): Boolean;

      { Сравнивает массивы бит }

 

    function Increase: TBits;

      { Массив бит интерпретируется как целое, которое

        увеличивается на единицу. При переполнении генерируется

        исключение EIntOverflow }

    function Reset: TBits;

      { Сброс всех битов массива }

 

    function ShiftLeft(BitsCount: Integer): TBits;

     { Сдвиг бит влево (аналог shl) }

    function ShiftLeftTo(DestBits: TBits;

      BitsCount: Integer): TBits;

      { Сдвиг бит влево двойной точности (аналог shld) }

 

  { Методы сдвига вправо используются при кодировании и

    декодировании потоков }

    function ShiftRight(BitsCount: Integer): TBits;

      { Сдвиг бит вправо (аналог shr) }

    function ShiftRightTo(DestBits: TBits;

      BitsCount: Integer): TBits;

      { Сдвиг бит вправо двойной точности (аналог shrd) }

 

    function ToString: String;

      { Возвращает строкое представление массива бит.

        Младший бит слева, старший – справа }

 

    function XorWith(Bits: TBits): TBits;

      { Сложение по модулю 2 (xor) }

 

  { Свойства класса }

 

    property Bit[Index: Integer]: TBit read GetBit write

     SetBit; default;

    property BitsCount: Integer read FBitsCount;

 

  { Прямой доступ к данным }

    property Data: PUnit read FData;

 

    property DataSize: Integer read FDataSize;

    property UnitsCount: Integer read FUnitsCount;

  end; { TBits }

2. Модуль «MathUtils.pas»

unit MathUtils;

 

interface

 

{ Факториал }

  function Factorial(N: LongWord): Extended;

 

{ Число сочетаний C из N по К.

  Функция используется кодом Рида-Маллера }

  function C(N, K: LongWord): LongWord;

3. Модуль «Code.pas»

unit Code;

 

interface

 

uses

  Classes, SysUtils, BitsUtils, Windows, Math, Contnrs;

 

const

  VERSION_MAJOR = 1;

  VERSION_MINOR = 0;

  VERSION_FULL:DWORD = (Word(VERSION_MAJOR) shl 16) or

                       Word(VERSION_MINOR);

 

{ Версия модуля Code, заложена для будущего контроля версий, при

  декодировании потоков }

 

type

{ THeader

  Заголовок в начале кодового потока }

  THeader = packed record

    Version: DWORD;

    DecodedSize: DWORD; { размер исходного потока в байтах }

  end;

 

{ Классы исключений }

  EECC = class(Exception);

  ECode = class(EECC);

  EWord = class(EBits);

  EDecoder = class(EECC);

  EEncoder = class(EECC);

  EInBuf = class(Exception);

  EOutBuf = class(Exception);

 

{ Класс TWord

  Информационное слово }

  TWord = class(TBits)