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

      { Метод реализует работу потока (thread) }

  end; { TCustomCodecThread }

 

 

{ TCodecThread

  Наследник TCustomCodecThread. Просто публикует свойства

  класса TCustomCodecThread }

  TCodecThread = class(TCustomCodecThread)

  public

    property Code;

    property EncodeMode;

    property InStream;

    property Interval;

    property OutStream;

 

    property OnDecodeCodeCreate;

    property OnProgress;

    property OnException;

  end; { TEncodeThread }

 

 

{ TFileEncodeThread

  Наследник TCustomCodecThread, надстройка. Позволяет сделать

  кодирование и декодирование файлов проще.

  Нужно указать имена исходного и целевого файлов, автоматически

  будут созданы соответствующие потоки } 

  TFileCodecThread = class(TCustomCodecThread)

  private

    FInputFileName: String;

      { Имя исходного файла }

    FOutputFileName: String;

      { Имя целевого файла }

 

  { Set методы свойств класса }

    procedure SetInputFileName(const Value: String);

    procedure SetOutputFileName(const Value: String);

 

  public

    destructor Destroy; override;

   

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

    property InputFileName: String read FInputFileName

      write SetInputFileName;

    property OutputFileName: String read FOutputFileName

      write SetOutputFileName;

 

  { Публикация свойств унаследованных от TCustomCodecThread }

    property EncodeMode;

    property Code;

    property Interval;

 

    property OnDecodeCodeCreate;

    property OnProgress;

    property OnException;

  end; { TFileEncodeThread }

5. Модуль «RM.pas»

Содержит реализацию кода Рида-Маллера.

 

unit RM;

 

interface

 

uses

  BitsUtils, Code, MathUtils, Windows, SysUtils, Classes;

 

{ Параметры кода Рида-Маллера по умолчанию }

const

  DEF_RM_M = 5;

  DEF_RM_R = 2;

   

type

  ERMCode = class(ECode);

  TRMCode = class(TCode)

  private

  { Параметры кода Рида-Маллера }

    FM: Integer;

    FR: Integer;

 

  { Новые параметры кода Рида-Маллера. Эти поля используются

    set-методами свойств R, M. Когда оба поля принимают ненулевые

    значения, проверяется допустимость этих параметров. Если

    они допустимы, то происходит создание новой порождающей матрицы

    и т.п. }

    FNewM: Integer;

    FNewR: Integer;

 

    FGkRows: array of Integer;

      { Массив числа строк в минорах G_k порождающей матрицы.

        Используется при декодировании для увеличения производительности }

 

    procedure FreeCode;

      { Освобождает память занятую порождающей матрицей, характеристическими

        векторами и FGkRows }

    procedure FreeCharacterVectors;

      { Освобождает память занятую характеристическими векторами }

    procedure FreeGeneratorMatrix;

      { Освобождает память занятую порождающей матрицей }

  protected

    FK: Integer;

      { Размер информационного свойства }

    FN: Integer;

      { Размер кодового слова }

    FG: array of TWord;

      { Порождающая матрица }

    FCharacterVectors: array of array of TWord;

      { Характеристические векторы для строк порождающей матрицы }

 

    procedure BuildGeneratorMatrix;

      { Строит порождающую матрицу }

    procedure BuildCharacterVectors;

      { Строит характеристические векторы для строк порождающей матрицы.

        Используется для ускорения процесса декодирования }

    procedure GenerateCode;

      { Проверяет допустимость FNewR и FNewM. Если все в порядке,

        вызывает FreeCode, а затем BuildGeneratorMatrix и

        BuildCharacterVectors.

        FNewR, FNewM сбрасываются в 0 }

    procedure FillE(var E: array of Integer; Monomial: array of Integer);

      { Заполняет множество E, состоящее из индексов переменных от 1 до M

        не входящих в моном Monomial. Используется при генерации

        характеристических векторов.

        Пример: M = 3. Monomial = [1]. Тогда E = [2, 3] }

    procedure NextIndexes(var Indexes: array of Integer);

      { Генерирует всевозможные перестановки на M элементах длины

       Length(Indexes).

        Используется при генерации строк порождающей матрицы }

 

  { Set-методы свойств }

    procedure SetM(Value: Integer);

    procedure SetR(Value: Integer);

 

  { Перекрытые методы, унаследованные от TCode }

    function GetK: Integer; override;

    function GetN: Integer; override;

    function GetFullName: String; override;

    class function GetName: String; override;

  public

    constructor Create(AOwner: TComponent); override;

    destructor Destroy; override;

 

  { Перекрытые методы, унаследованные от TCode }

    procedure Encode(Word: TWord; CodeWord: TCodeWord); override;

    procedure Decode(RecievedWord: TCodeWord; Word: TWord); override;

 

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

    property K: Integer read GetK;

    property N: Integer read GetN;

 

  published

  { Published свойства автоматически сохраняются при записи класса в

    поток, и восстанавливаются при создании класса из потока.

    При декодировании это позволяет создать код Рида-Маллера

    с теми параметрами, которые использовались при кодировании }

    property M: Integer read FM write SetM default DEF_RM_M;

    property R: Integer read FR write SetR default DEF_RM_R;

  end; { TRMCode }

6. Модуль «BCH.pas»

Содержит реализацию кода БЧХ(5, 15, 7).

 

unit BCH;

 

interface

 

uses

  SysUtils, Code, BitsUtils, Windows, Math, Classes;

 

const

{ Параметры кода }

  BCH_K = 5;

  BCH_N = 15;

  BCH_D = 7;

 

{ Число слов длины 15 и кодовых слов }

  BCH_WORDS_COUNT = 32768; { 2^15 }

  BCH_CODEWORDS_COUNT = 32; { 2^5 }

 

{ Порождающий многочлен для БЧХ(5, 15, 7):

    x^10 + x^8 + x^5 + x^4 + x^2 + x + 1 }

 

{ Порождающая матрица }

  BCH_GEN: array[0..BCH_K-1, 0..BCH_N-1] of TBit =

    ( (1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0),

      (0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0),

      (0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0),

      (0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0),

      (0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1)

    );

 

type

{ Класс исключительной ситуации }

  EBCHCode = class(ECode);

 

{ БЧХ код (5, 15, 7)

  Используется табличное кодирование и декодирование }

 

  TBCHCode = class(TCode)

  protected

  { Параметры кода }

    FK: Integer;

    FN: Integer;

  { Таблица декодирования }

    FDecodeTable: array[0..BCH_WORDS_COUNT - 1] of Byte;

  { Таблица кодирования }

    FEncodeTable: array[0..BCH_CODEWORDS_COUNT - 1] of Word;

 

  { Построение таблицы декодирования.

    Cлова разбиваются на смежные классы. В каждом

    смежном классе выбирается лидер и заполняется таблица декодирования }

    procedure BuildDecodeTable;

 

  { Построение таблицы кодирования }

    procedure BuildEncodeTable;

 

  { Перекрытые методы, унаследованные от TCode }

    function GetD: Integer; override;

    function GetK: Integer; override;

    function GetN: Integer; override;

    function GetFullName: String; override;

    class function GetName: String; override;

  public

    constructor Create(AOwner: TComponent); override;

    constructor CreateNew;

 

  { Кодирование

    Информационное слово рассматривается как индекс (0..31).

    Кодовое слово получается копированием содержимого таблицы кодирования,

    находящегося по указанному индексу }

    procedure Encode(Word: TWord; CodeWord: TCodeWord); override;

 

  { Декодирование

    Полученное слово рассматривается как индекс (0..32767}.

    Информационного слово получается копированием содержимого таблицы

    декодирования, находящегося по указанному индексу }

    procedure Decode(RecievedWord: TCodeWord; Word: TWord); override;

 

  { Свойства унаследованные от TCode }

    property K: Integer read GetK;

    property N: Integer read GetN;

  end; { TBCHCode }

7. Прочие модули

• MainFrm.pas – cодержит класс главного окна программы Magic Code.
• CodeWordFrm.pas – содержит класс окна, в котором можно вводить информационное слово и в ответ получать кодовое слово.
• CodecFrm.pas – класс окна визуализации процессов кодирования и декодирования файлов.
• AnalisFrm.pas – класс окна анализа кода. Окно содержит результаты анализа, обновляемые в реальном времени. Его можно закрыть в любой момент, не обязательно дожидаться окончания анализа.
• ImageDemoFrm.pas – класс окна демонстрации передачи изображения по зашумленному каналу.

4. Заключение

В результате проделанной работы были реализованы:

1. гибкая, легко расширяемая система, основанная на принципах объектно-ориентированного программирования;
2. класс кода БЧХ(5, 15, 7);
3. класс кода Рида-Маллера с произвольными параметрами;
4. наборы классов для операций кодирования и декодирования;

 

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

Аттестационная работа имеет хорошие перспективы для дальнейшего развития, например, интересной представляется возможность создания универсального класса для БЧХ-кодов, а также повышение производительности до качественно нового уровня. Еще более интересной является задача исследования поведения кодов в ситуациях, когда возникающие при передаче информации ошибки превышают конструктивные способности кода их исправлять. Т.е. если код по построению способен исправлять ошибки веса не больше 3-х, то как он проявит себя с ошибками веса 4 и выше?

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

5. Литература

1. Robert H. Morelos-Zaragoza, «The Art of Error Correcting Coding», Wiley, 2002.
2. Ben Cooke, «Reed_Muller Error Correcting Codes».
3. William J. Gilbert, W. Keith Nicholson, «Modern algebra with applications», 2nd ed, Wiley, 2004.
4. М. Н. Аршинов, Л. Е. Садовский, «Коды и математика (рассказы о кодировании)», М.: Наука, 1983. – 144с.
5. Лидовский В. В., «Теория информации», М.:2003. – 112с.

¹ Назначение тех или иных методов можно найти в разделе «Описание модулей», а также в комментариях к исходному коду проекта Magic Coder.