Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Омский государственный университет им. Ф.М. Достоевского
Математический факультет
Кафедра математической логики и логического программирования
Программная реализация алгоритмов кодирования и декодирования для БЧХ-кодов и кодов Рида-Маллера
Аттестационная работа
студента группы ММ-102
Антонова В.И.
_______________ (подпись)
Научный руководитель
доцент, кандидат ф.- м. наук
Ашаева Ю.М.
_______________ (подпись)
Омск - 2005
Содержание
ВВЕДЕНИЕ.. 3
1. Постановка задачи. 4
2. Реализация кодов. 5
2.1. Общие сведения. 5
2.2. БЧХ(5, 15, 7) 5
2.3. Код Рида-Маллера. 5
3. Magic Coder 7
3.1. Руководство пользователя. 7
3.1.1. Меню «Файл». 7
3.1.2. Меню «Код». 7
3.2. Добавление новых кодов. 8
3.3. Описание модулей программы.. 9
3.3.1. Модуль «BitsUtils.pas». 9
3.3.2. Модуль «MathUtils.pas». 12
3.3.3. Модуль «Code.pas». 12
3.3.4. Модуль «CodeThreads.pas». 20
3.3.5. Модуль «RM.pas». 25
3.3.6. Модуль «BCH.pas». 27
3.3.7. Прочие модули. 29
4. Заключение. 30
5. Литература. 31
ВВЕДЕНИЕ
С ростом использования электроники и компьютеров, растет потребность в быстрой и надежной передаче информации по радио- и телефонным каналам связи, а также от одного устройства к другому. В любом канале связи присутствуют шумы – сигналы, которые могут искажать передаваемую по каналу информацию. С этими искажениями можно бороться, преобразуя передаваемую информацию при помощи кода, который будет обнаруживать, и исправлять ошибки. Так, например, в 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 – задает длину кодового слова, 25
=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. Добавление новых кодов
Если вы хотите добавить поддержку нового кода, то вы должны сделать следующее:
Добавить новый модуль к проекту MagicCoder.
dpr.
В полученном модуле создать наследника класса TCode
, например, TMyCode
.
Перекрыть методы[1]
: GetK GetN GetName Encode Decode
При желании перекрыть методы: GetD GetDescription GetFullName
Добавить в модуль секции initialization
и finalization
следующего содержания: initialization
RegisterCode(TMyCode) finalization
UnRegisterCode(TMyCode)
Этого будет достаточно для того, чтобы добавить полную поддержку нового кода.
3.3. Описание модулей программы
Во всех модулях программы обработка ошибок основана на механизме исключительных ситуаций (exceptions). Описание модулей программы выполнено в виде комментариев в стиле Delphi к объявлениям классов, их полей и методов; функций и констант.
3.3.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 }
3.3.2. Модуль
«MathUtils.pas»
unit
MathUtils;
interface
{
Факториал
}
function
Factorial(N: LongWord): Extended;
{ Число сочетаний
C
из
N
по К.
Функция используется кодом Рида-Маллера }
function
C(N, K: LongWord): LongWord;
3.3.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)
public
{
Скалярное умножение двух слов
}
function
ScalarMul(Word: TBits): Integer;
{ Слово
Self
и
Word
рассматриваются как векторы }
{
Вес
слова
}
function
Weight: Integer;
end
;
{ Класс
TCodeWord
Кодовое слово }
TCodeWord = TWord;
{ Forward declaration }
TCode = class
;
{
Класс
TInBuf
Буфер ввода. Используется для чтения бит из потока }
TInBuf = class
(TObject)
private
FInStream: TStream;
FBuf: TBits;
FBufRest: Integer;
{ число оставшихся (с конца) значащих бит в буфере }
public
constructor
Create(InStream: TStream;
UnitsCount: Cardinal = 4096);
{ InStream - поток, из которого будет производится чтение
UnitsCount - число элементов
TUnit
во входном буфере }
destructor
Destroy; override
;
procedure
Read
(Word: TWord);
{ Читает следующие Word.BitsCount бит из входного потока
Если во входном потоке осталось меньше бит чем
BitsCount, то оставшиеся биты приравниваются 0 }
function
EoS: Boolean;
{ Возвращает истину, если входной поток закончился }
property
InStream: TStream read
FInStream;
end
; { TInBuf }
{ Класс
TOutBuf
Используется для записи бит в поток }
TOutBuf = class
(TObject)
private
FOutStream: TStream;
FBuf: TBits;
FBufRest: Integer;
{ число оставшихся значащих бит в буфере }
public
constructor
Create(OutStream: TStream;
UnitsCount: Cardinal = 4096);
{ OutStream - поток, в который будет производится запись
UnitsCount - число элементов
TUnit
в буфере }
destructor
Destroy; override
;
{ Уничтожает объект, предварительно вызвав Flush }
procedure
Write
(Word: TWord);
{ Записывает биты слова
Word
в буфер, вытесняя из него
имеющиеся данные в поток вывода }
procedure
Flush;
{ Сбрасывает оставшуюся информацию из буфера в поток }
property
OutStream: TStream read
FOutStream;
end
; { TOutBuf }
{ TCode
Базовый
класс
для
кодов
}
TCode = class
(TComponent)
protected
FD: Integer;
{ Это поле хранит минимальное расстояние кода. Оно
вычисляется методом
GetD
}
function
GetD: Integer; virtual
;
{ Вычисляет минимальное расстояние кода перебором.
В наследниках рекомендуется перекрыть этот метод. }
function
GetDescription: String; virtual
;
{
Описание
кода
.
Возвращает
пустую
строку
.
Наследники могут перекрыть
этот метод }
function
GetK: Integer; virtual
; abstract
;
{ Возвращает размер информационного слова.
Наследники должны перекрыть этот метод }
function
GetN: Integer; virtual
; abstract
;
{ Возвращает размер кодового слова.
Наследники должны перекрыть этот метод }
function
GetFullName: String; virtual
;
{ Возвращает полное название кода, например,
Код Рида-Маллера(2, 5).
Наследники могут перекрыть этот метод. По умолчанию
Он возвращает результат
GetName
}
class
function
GetName: String; virtual
;
{ Возвращает название кода.
Наследники должны перекрыть этот метод }
public
procedure
Encode(Word: TWord; CodeWord: TCodeWord); virtual
;
abstract
;
{ Преобразует информационное слово в кодовое
Word - информационное слово. Размер информационного
слова должен
быть не меньше чем K. При кодировании
используются лишь первые K бит
информационного слова
CodeWord - кодовое слово. Размер должен быть не
меньше чем N
Наследники должны перекрыть этот метод }
procedure
Decode(RecievedWord: TCodeWord; Word: TWord);
virtual
; abstract
;
{ Декодирование
RecievedWord - полученное слово, которое будет
декодировано. Размер должен быть
не меньше N. Используются лишь
первые N бит слова
Word - декодированное слово. Размер должен
быть не меньше K
Наследники должны перекрыть этот метод }
{
Свойства
}
property
Description: String read
GetDescription;
property
FullName: String read
GetFullName;
property
Name: String read
GetName;
property
D: Integer read
GetD;
property
K: Integer read
GetK;
property
N: Integer read
GetN;
end
; { TCode }
{ Тип класса для потоковой системы }
TPersistentCode = class
of
TCode;
{
TCodeListViewer
Класс для просмотра зарегистрированных в потоковой системе
кодов
.
Является прослойкой между приложением и классом
TCodeList
, который находится в части
реализации модуля (
implementation
) и, следовательно, не виден
вне этого модуля. Это сделано для повышения надежности
системы в целом, т.к.
TCodeList
играет огромную роль в ее
работе
}
TCodeListViewer = class
(TObject)
private
function
GetCount: Integer;
{ Возвращает число кодов зарегистрированных в потоковой
системе
}
function
GetCodeClassName(Index: Integer): String;
{ Возвращает имя класса кода по индексу. Например,
класс кода Рида-Маллера имеет имя
TRMCode
}
function
GetCodeName(Index: Integer): String;
{ Возвращает название кода по индексу. Т.е. результат
вызова метода
GetName
для соответствующего кода. }
function
GetIndexOfCodeName(CodeName: String): Integer;
{ Возвращает индекс первого найденного кода название
которого совпало с заданным. Если совпадений не найдено,
то возвращается -1 }
function
GetIndexOfCodeClassName(CodeClassName:
String): Integer;
{ Возвращает индекс первого найденного кода, имя класса
которого
совпало
с
заданным
.
Если совпадений не
найдено, то возвращается -1
}
public
{
Свойства
}
property
Count: Integer read
GetCount;
property
CodeNames[Index: Integer]: String read
GetCodeName;
property
CodeClassNames[Index: Integer]: String read
GetCodeClassName;
property
IndexOfCodeName[CodeName: String]: Integer read
GetIndexOfCo
property
IndexOfCodeClassName[CodeClassName: String]:
Integer read
GetIndexOfCodeClassName;
end
;
{
Функции общего назначения
}
{ Вес слова (количество ненулевых бит) }
function
WordWeight(const
Word; Len: Integer): Integer;
{ Регистрация кода в потоковой системе.
Незарегистрированный код не может быть использован при
декодировании
из
потока
}
procedure
RegisterCode(C: TPersistentCode);
{ Удаление кода из потоковой системы }
procedure
UnRegisterCode(C: TPersistentCode);
{ Проверка параметров при кодировании и декодировании }
procedure
CheckEncoderParams(InStream, OutStream:
TStream; Code: TCode);
procedure
CheckDecoderParams(InStream, OutStream:
TStream; Code: TCode = TCode($1));
{ Кодирование и декодирование потоков
При кодировании в выходной поток записывается
заголовок следующего содержания:
Версия - версия кодового потока
Размер входного потока в байтах
Информация о коде (сериализованный TCode)
Далее, до конца потока, следуют упакованные
кодовые
слова
При декодировании, сначала анализируется заголовок.
Если в нем указана неизвестная версия то, генерируется
Исключение
EDecoder
. Затем происходит попытка создать
код, используя записанную в потоке информацию о нем. После
чего, начинается само декодирование }
procedure
DecodeStream(InStream, OutStream: TStream);
procedure
EncodeStream(InStream, OutStream: TStream;
Code: TCode);
{ Кодирование и декодирование файлов
Эти процедуры являются надстройками над
DecodeStream
и
EncodeStream
}
procedure
DecodeFile(InputFileName, OutputFileName: String);
procedure
EncodeFile(InputFileName, OutputFileName: String; Code: TCode);
{ Кодирование и декодирование без заголовка
При кодировании в поток не записывается дополнительная
информация (заголовок).
Поэтому при декодировании нужно явно указывать код,
которым нужно его производить }
procedure
RawDecodeStream(InStream, OutStream: TStream;
Code: TCode);
procedure
RawEncodeStream(InStream, OutStream: TStream;
Code: TCode);
{ Запись заголовка в поток
}
procedure
WriteHeader(InStream, OutStream: TStream;
Code: TCode);
implementation
type
{ TCodeList
Этот класс хранит информацию о кодах зарегистрированных в
Потоковой системе системе }
TCodeList = class
(TObject)
private
FCodeList: TClassList;
{
Список классов
}
function
GetCount: Integer;
{ Число элементов в списке классов }
function
GetCodeClassName(Index: Integer): String;
{ Имя класса кода по индексу, например
TRMCode
}
function
GetCodeName(Index: Integer): String;
{ Название кода по индексу, например Код Рида-Маллера }
public
constructor
Create;
destructor
Destroy; override
;
function
Add(Code: TPersistentCode): Integer;
{ Добавляет класс в список, если его там нет,
и возвращает его индекс.
Если класс уже есть, то просто возвращается его индекс }
procedure
Delete(Code: TPersistentCode);
{ Удаляет класс из списка }
{ Свойства }
property
Count: Integer read
GetCount;
property
CodeClassNames[Index: Integer]: String read
GetCodeClassName;
property
CodeNames[Index: Integer]: String read
GetCodeName;
end
; { TCodeList }
var
CodeList: TCodeList;
{ Экземпляр класса
TCodeList
. Создается в секции
инициализации данного модуля. Уничтожается в секции
финализации
}
3.3.4. Модуль
«CodeThreads.pas»
Модуль содержит классы, реализующие кодирование и декодирование в отдельном потоке (thread). Эти классы используются тестовой программой для того, чтобы визуализировать результаты работы в реальном времени, а также для предоставления возможности пользователю отменить операции кодирования и декодирования.
unit
CodeThreads;
interface
uses
SysUtils, Code, Forms, Classes, Windows;
const
DEF_ONPROGRESS_INTERVAL = 500;
{ интервал в миллисекундах между событиями
OnProgress
. Потоки (
thread
)
генерируют события
OnProgress
для того чтобы основная программа
смогла показать пользователю текущее состояние работы потока }
type
TProgressEvent = procedure
(Sender: TObject;
BitsProcessed: Int64) of
object;
{
Описание
обработчика
события
OnProgress.
Sender
– объект, который сгенерировал событие
OnProgress
BitsProcessed -
число
обработанных
бит
}
TDecodeCodeCreateEvent = procedure
(Sender: TObject;
ACode: TCode) of
object;
{
Описание
обработчика
события
OnDecodeCodeCreate.
Данное событие генерируется после того, как поток (
thread
) создаст
код при декодировании. Это позволяет программе получить сведения о
коде, которым были кодированы исходные данные }
{ TCustomCodecThread
Класс для кодирования и декодирования потоков с возможностью
обработки прогресса и отмены операции }
TCustomCodecThread = class
(TThread)
private
FCode: TCode;
{ код, которым производится кодирование }
FDecodeCode: TCode;
{ код использующийся для декодирования, создается автоматически на
основе информации во входном потоке }
FOutStream: TStream;
{
поток вывода
}
FInStream: TStream;
{
поток ввода
}
FWorking: Boolean;
{ Признак того, что поток (
thread
) в данный момент работает }
FInterval: Cardinal;
{ Интервал в миллисекундах, через который генерируются события
OnProgress }
FBitsProcessed: Int64;
{ Число обработанных бит (при кодировании и декодировании) }
FException: Exception;
{ Хранит объект исключительной ситуации на время работы
обработчика
события
OnException }
FEncodeMode: Boolean;
{ Задает режим работы потока (
thread
).
Если истина, то кодирование. Если ложь - декодирование }
FOnException: TExceptionEvent;
{
Указатель
на
обработчик
события
OnException.
Данное событие генерируется при возникновении исключительной
ситуации во время процесса кодирования и декодирования }
FOnProgress: TProgressEvent;
{ Указатель на обработчик события
OnProgress
.
Событие периодически генерируется во время процессов
кодирования и декодирования }
FOnDecodeCodeCreate: TDecodeCodeCreateEvent;
{ Указатель на обработчик события
OnDecodeCodeCreate
}
{
Set
методы для свойств класса. Большинство из
них игнорируют новые значения для свойств класса
если
FWorking = True
}
procedure
SetCode(const
Value: TCode);
procedure
SetInterval(const
Value: Cardinal);
procedure
SetInStream(const
Value: TStream);
procedure
SetOutStream(const
Value: TStream);
procedure
SetEncodeMode(const
Value: Boolean);
{
Методы вызова обработчиков событий
}
procedure
CallOnDecodeCodeCreate;
procedure
CallOnProgress;
procedure
ExceptionHandler;
protected
{ Проверка параметров перед началом кодирования
В случае обнаружения ошибки - исключение }
procedure
EncodeCheck; virtual
;
{ Проверка параметров перед декодированием
В случае ошибки - исключение }
procedure
DecodeCheck; virtual
;
{ Запись заголовочных данных (
THeader
и информация о коде) в
выходной
поток
}
procedure
WriteHeaders; virtual
;
{ Чтение заголовочных данных из входного потока }
procedure
ReadHeaders; virtual
;
{ Кодирование входного потока и его запись в выходной поток.
Наследники могут перекрывать этот метод, если хотят изменить
процесс кодирования }
procedure
EncodeProc; virtual
;
{ Декодирование входного потока и его запись в выходной поток.
Наследники могут перекрывать этот метод, если хотят изменить
процесс
декодирования
}
procedure
DecodeProc; virtual
;
{
Свойства класса
}
property
Code: TCode read
FCode write
SetCode;
property
DecodeCode: TCode read
FDecodeCode;
{ Код использующийся при декодировании.
DecodeCode <> nil только во время процесса декодирования.
После окончания декодирования снова становится равным nil }
property
EncodeMode: Boolean read
FEncodeMode write
SetEncodeMode;
property
InStream: TStream read
FInStream write
SetInStream;
property
OutStream: TStream read
FOutStream write
SetOutStream;
property
Working: Boolean read
FWorking;
{
События
}
property
OnDecodeCodeCreate: TDecodeCodeCreateEvent
read
FOnDecodeCodeCreate write
FOnDecodeCodeCreate;
property
OnProgress: TProgressEvent read
FOnProgress write
FOnProgress;
property
Interval: Cardinal read
FInterval write
SetInterval;
property
OnException: TExceptionEvent read
FOnException
write
FOnException;
public
constructor
Create(AEncodeMode: Boolean = True);
procedure
Execute; override
;
{ Метод реализует работу потока (
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 }
3.3.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 }
3.3.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 }
3.3.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с.
[1]
Назначение тех или иных методов можно найти в разделе «Описание модулей», а также в комментариях к исходному коду проекта Magic Coder.