Древовидный кодер и декодер с использованием XML

Чтобы использовать нулевое начальное состояние, принимаемое по умолчанию, задайте параметр initstate равным 0 или [].

[code, finalstate] = convenc (…)

Кодирует входное сообщение и, помимо этого, возвращает в скалярном выходном параметре finalstate заключительное внутреннее состояние кодера. Формат параметра finalstate такой же, как у входного параметра initstate.

Примеры использования кодера приведены в приложении 1.

3.

2. VITDEC — Декодирование сверточного кода с помощью алгоритма Витерби.

Синтаксис:

decoded = vitdec (code, trellis, tblen, opmode, dectype);

decoded = vitdec (code, trellis, tblen, opmode,'soft', nsdec);

decoded = vitdec (…,'cont',…, initmetric, initstates, initinputs);

[decoded, finalmetric, finalstates, finalinputs] = vitdec (…,'cont',…);

Описание:

decoded = vitdec (code, trellis, tblen, opmode, dectype)

Производит декодирование вектора code с помощью алгоритма Витерби. MATLAB-структура trellis описывает таблицу переходов используемого сверточного кода. Подробная информация о назначении полей этой структуры приведена на странице с описанием функции istrellis. Входной вектор code может содержать один или несколько символов, каждый из которых состоит из log2(trellis.numOutputSymbols) бит. Результат декодирования — выходной двоичный вектор decoded — содержит столько же символов, сколько и входной вектор code, при этом каждый декодированный символ состоит из log2(trellis.numInputSymbols) бит. Скалярный входной параметр tblen — положительное целое число, задающее глубину просмотра решетки при декодировании.

Строковый параметр opmode задает режим работы декодера и используемые предположения относительно работы кодера, сгенерировавшего входной вектор code. Возможные значения данного параметра приведены в табл. 1.

Таблица 1. Возможные значения входного параметра opmode

Значение Смысл 'trunc' Начальное внутреннее состояние кодера считается нулевым. Декодер производит обратную трассировку от состояния с наилучшей метрикой 'term' Начальное и конечное внутренние состояния кодера считаются нулевыми. Декодер производит обратную трассировку от нулевого внутреннего состояния 'cont' Начальное внутреннее состояние кодера считается нулевым. Декодер производит обратную трассировку от состояния с наилучшей метрикой. Декодированные символы появляются в выходном векторе с задержкой на tblen символов Строковый параметр dectype задает тип декодирования, используемый декодером. От значения этого параметра зависит и вид требуемых входных данных в векторе code. Возможные значения данного параметра приведены в табл. 2.

Таблица 2. Возможные значения входного параметра dectype

Значение Смысл 'unquant' Вектор code содержит вещественные числа, при этом 1 соответствует логическому нулю, а -1 представляет логическую единицу (жесткое декодирование) 'hard' Вектор code содержит двоичные данные, то есть каждый из его элементов может быть равен нулю или единице (жесткое декодирование) 'soft' Мягкое декодирование, описание синтаксиса для данного режима приводится ниже. Наличие входного параметра nsdec в этом случае является обязательным Синтаксис для реализации мягкого декодирования

— decoded = vitdec (code, trellis, tblen, opmode,'soft', nsdec)

Производит мягкое декодирование вектора code. Входной вектор code должен содержать целые числа в диапазоне от 0 до 2nsdec — 1, при этом значение 0 представляет бит, с наибольшей достоверностью равный нулю, а значение 2nsdec — 1 означает бит, с наибольшей достоверностью равный единице. Промежуточные значения соответствуют промежуточным степеням достоверности принятой двоичной информации.

Дополнительные варианты синтаксиса для реализации блочного декодирования

— decoded = vitdec (…,'cont',…, initmetric, initstates, initinputs)

То же, что предыдущие варианты синтаксиса, но начальное состояние декодера (текущие метрики, трассы выживших путей и последовательности соответствующих им символов) задаются входными параметрами initmetric, initstates и initinputs соответственно. Вещественные числа в векторе initmetric, длина которого равна числу состояний кодера, задают начальные метрики для всех внутренних состояний. Каждая из матриц initstates и initinputs, совместно задающих начальное состояние памяти кодера, должна иметь trellis. numStates строк и tblen столбцов. Матрица initstates должна содержать целые числа в диапазоне от 0 до trellis. numStates-1. Если схема кодера предполагает наличие нескольких входных битовых потоков, то состояние сдвигового регистра, принимающего первый входной битовый поток, соответствует младшим битам элементов матрицы initstates, а состояние сдвигового регистра, принимающего последний поток, — старшим битам этих величин. Матрица initinputs должна содержать целые числа в диапазоне от 0 до trellis. numInputSymbols-1. Чтобы использовать значения по умолчанию для всех этих входных параметров, можно задать их в виде пустых матриц: [],[],[].

— [decoded, finalmetric, finalstates, finalinputs] = vitdec (…,'cont',…)

То же, что предыдущие варианты синтаксиса, но три дополнительных выходных параметра содержат конечные значения метрик (finalmetric), трассы выживших путей (finalstates) и последовательности соответствующих им символов (finalinputs). Выходной параметр finalmetric является вектором длиной trellis. numStates, содержащим конечные значения метрик для всех внутренних состояний. Выходные параметры finalstates и finalinputs являются матрицами, содержащими trellis. numStates строк и tblen столбцов. Их формат аналогичен формату матриц initstates и initinputs.

Примеры использования кодера приведены в приложении 2.

3.

3. RSDECOF — Декодирование текстового файла, закодированного с использованием кода Рида-Соломона.

Синтаксис:

rsdecof (file_in, file_out);rsdecof (file_in, file_out, err_cor);

Описание:

Данная функция является обратной по отношению к функции rsencof — она осуществляет декодирование файла, закодированного с помощью функции rsencof.

— rsdecof (file_in, file_out)

Декодирует текстовый (ASCII) файл file_in, созданный с помощью функции rsencof с использованием кода Рида— Соломона (117, 127), исправляющего 5-кратные ошибки. Декодированное сообщение записывается в файл file_out. Параметры file_in и file_out должны быть строками.

Если число символов в файле file_in не делится на 127, то функция дополняет файл символами char (4). Если кодирование и декодирование файла выполнялись функциями rsencof и rsdecof соответственно, в конце декодированного файла может содержаться некоторое количество символов char (4), которых не было в исходном файле.

rsdecof (file_in, file_out, err_cor)

То же, что и предыдущий вариант синтаксиса, но параметр err_cor задает корректирующую способность кода (кратность исправляемых ошибок). Длина блока равна 127 символам. Длина сообщения в блоке составляет 127−2*err_cor. Значение параметра err_cor должно совпадать с тем, что использовалось функцией rsencof при создании файла file_in.

Примеры использования кодера приведены в приложении 3.

3.

4. RSENCOF — Кодирование текстового файла с использованием кода Рида-Соломона.

Синтаксис:

rsencof (file_in, file_out);rsencof (file_in, file_out, err_cor);

Описание:

rsencof (file_in, file_out)

Кодирование текстового (ASCII) файла file_in с использованием кода Рида—Соломона (127, 117). Данный код позволяет исправлять 5-кратные ошибки. Закодированный текст записывается в файл file_out. Параметры file_in и file_out должны быть строками.

— rsencof (file_in, file_out, err_cor)

То же, что и предыдущий вариант синтаксиса, но параметр err_cor задает корректирующую способность кода (кратность исправляемых ошибок). Длина блока равна 127 символам. Длина сообщения в блоке составляет 127−2*err_cor.

Если число символов в файле file_in не делится на 127−2*err_cor, то функция дополняет файл символами char (4).

Примеры использования кодера приведены в приложении 3.

3.

5. HUFFMANENCO — Кодер Хаффмана.

Синтаксис:

comp = huffmanenco (sig, dict)

Описание:

comp = huffmanenco (sig, dict)

Кодирует сигнал sig с использованием кода Хаффмана, описываемого словарем dict. Входной параметр sig может быть числовым вектором, числовым массивом ячеек или символьным массивом ячеек. Если sig — массив ячеек, он должен быть строкой или столбцом. Второй входной параметр dict должен быть массивом ячеек размером N на 2, где N — объем алфавита источника. Первый столбец массива dict представляет символы источника, второй столбец — соответствующие кодовые слова. Каждое кодовое слово должно быть представлено числовым вектором-строкой, и ни одно кодовое слово в массиве dict не должно быть префиксом в другом кодовом слове. Создать массив dict можно с помощью функции huffmandict.

Примеры использования кодера приведены в приложении 4.

Заключение

.

В наше время самым ценным достоянием считается информация. И этот факт ставит важнейшую задачу ее сохранения, как в процессе ее обработки и передачи, так и в процессе ее хранения. Единственным, известным средством, позволяющим корректно решать эту задачу, является теория кодирования информации. В работе были рассмотрены некоторые виды и приемы кодирования. На примере кодирования XML-файла продемонстрированы способ шифрования информации, методами кодирования. Описаны функции кодирования вычислительного редактора Matlab.

Приложения.

Приложение 1.

Пример 1.

Приведенная ниже команда кодирует пять случайных двухбитовых символов с использованием сверточного кода, имеющего скорость кодирования 2/3. Структурная схема этого кодера приведена на странице с описанием функции poly2trellis.

code1 = convenc (randint (10,1,2,123), poly2trellis ([5 4],[27 33 0; 0 5 13]));

Пример 2.

Приведенные ниже команды создают структуру таблицы переходов в явном виде, а затем с помощью функции convenc производят кодирование десяти однобитовых символов. Решетчатая диаграмма для используемого в данном примере кода (его скорость равна ½) показана на рисунке.

trel = struct ('numInputSymbols', 2,'numOutputSymbols', 4,…'numStates', 4,'nextStates',[0 2;0 2;1 3;1 3],…

'outputs',[0 3;1 2;3 0;2 1]);

code2 = convenc (randint (10,1), trel);

Пример 3.

Приведенные ниже команды демонстрируют использование дополнительных параметров initstate и finalstate для того, чтобы кодировать сообщение по частям, вызывая функцию convenc несколько раз. Объединенный выходной вектор [code3; code4] совпадает с результатами кодирования, полученными в Примере 1 (вектор code1).

trel = poly2trellis ([5 4],[27 33 0; 0 5 13]);

msg = randint (10,1,2,123);

% Encode part of msg, recording final state for later use. code3, fstate] = convenc (msg (1:6), trel);% Encode the rest of msg, using state as an input argument. code4 = convenc (msg (7:10), trel, fstate);

Приложение 2.

Пример 1.

В данном примере производится сверточное кодирование случайных данных с последующим добавлением шума. Далее выполняется декодирование зашумленного сигнала, при этом иллюстрируются все три типа декодирования, поддерживаемых функцией vitdec. Обратите внимание на то, что при использовании неквантованных входных данных (dectype = 'unquant'), а также в случае мягкого декодирования (dectype = 'soft') результат работы кодирующей функции convenc имеет не тот вид, который требуется для декодирования с помощью функции vitdec. В этих случаях кодированный вектор ncode перед подачей на вход функции vitdec необходимо подвергнуть дополнительным преобразованиям.

trel = poly2trellis (3,[6 7]); % Описание кодаmsg = randint (100,1,2,123); % Случайные данныеcode = convenc (msg, trel); % Кодированиеncode = rem (code + randerr (200,1,[0 1;.95 .05]), 2); % Добавляем шумtblen = 3; % Глубина просмотра при декодировании% Вариант 1 — жесткое декодированиеdecoded1 = vitdec (ncode, trel, tblen,'cont','hard');% Вариант 2 — жесткое декодирование с неквантованным входом ucode = 1−2*ncode; % преобразуем 0 в +1, а 1 в -1decoded2 = vitdec (ucode, trel, tblen,'cont','unquant');% Вариант 3 — мягкое декодирование% Производим восьмиуровневое квантование зашумленного сигнала[x, qcode] = quantiz (1−2*ncode,[-.75 -.5 -.25 0 .25 .5 .75],…[7 6 5 4 3 2 1 0]); % Значения в векторе qcode лежат в диапазоне от 0 до 2³−1.decoded3 = vitdec (qcode', trel, tblen,'cont','soft', 3);% Вычисляем вероятности ошибок с учетом того, что выходной сигнал% декодера задержан на tblen символов[n1,r1] = biterr (decoded1(tblen+1:end), msg (1:end-tblen));[n2,r2] = biterr (decoded2(tblen+1:end), msg (1:end-tblen));[n3,r3] = biterr (decoded3(tblen+1:end), msg (1:end-tblen));disp (['The bit error rates are: ', num2str ([r1 r2 r3])])

The bit error rates are: 0.20 619 0.20 619 0.20 619

Пример 2.

Данный пример демонстрирует использование дополнительных параметров функции vitdec для того, чтобы декодировать сообщение по частям, вызывая функцию vitdec несколько раз. Объединенный декодированный вектор [decoded4;decoded5] совпадает с результатами декодирования, полученными при обработке всего сообщения целиком (вектор decoded6).

trel = poly2trellis (3,[6 7]);code = convenc (randint (100,1,2,123), trel);% Декодируем первую половину сигнала и сохраняем текущее состояние декодера[decoded4,f1,f2,f3] = vitdec (code (1:100), trel, 3,'cont','hard');% Декодируем вторую половину сигнала, используя сохраненное состояние кодераdecoded5 = vitdec (code (101:

200), trel, 3,'cont','hard', f1, f2,f3);% Декодируем весь сигнал целикомdecoded6 = vitdec (code, trel, 3,'cont','hard');isequal (decoded6,[decoded4; decoded5])

ans =

Приложение 3.

Файл matlabroot/toolbox/comm/comm/oct2dec.m содержит текст справки об использовании функции oct2dec пакета Communications. Приведенные ниже команды осуществляют кодирование этого файла с помощью функции rsencof и его декодирование с помощью функции rsdecof.

file_in = [matlabroot '/toolbox/comm/comm/oct2dec.m'];file_out = 'encodedfile'; % Имя кодированного файлаrsencof (file_in, file_out) % Кодированиеfile_in = file_out;file_out = 'decodedfile'; % Имя декодированного файлаrsdecof (file_in, file_out) % Декодирование Для просмотра текстов исходного и декодированного файла в среде MATLAB используйте приведенные ниже команды.

type oct2dec. mtype decodedfile

Приложение 4.

Приведенный ниже код кодирует вектор случайных данных, которые имеют заданное распределение вероятности.

symbols = [1:6]; % Алфавит источника

p = [.5 .125 .125 .125 .0625 .0625]; % Распределение вероятностей

[dict, avglen] = huffmandict (symbols, p); % Создание словаря

actualsig = randsrc (100,1,[symbols; p]); % Случайные данные с распределением p

comp = huffmanenco (actualsig, dict); % Кодирование данных

Список литературы

Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В., Основы криптографии: Учебное пособие. — М. Гелиос АРВ, 2001.

Блейхер Р., Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986

Борн Г., Форматы данных

Киев: Торгово-издательское бюро BHV, 1995

Кенцл Т., Форматы файлов InternetСПб: Питер, 1997

Лидовский В. В. Теория информации. М. Компания Спутник, 2004.

Нефедов В. Н., Осипова В. А. Курс дискретной математики. М.: МАИ, 1992

Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.

Чисар И., Кернер Я. Теория информации. М.: Мир, 1985.

Яглом А., Яглом И Вероятность и информация, М.: Наука, 1973.

Sayod, Khalid, Introduction to Data Compression, San Francisco, Morgan Kaufmann, 2000.

http://matlab.exponenta.ru/communication/book2/index.php

Яглом А., Яглом И Вероятность и информация, М.: Наука, 1973.

Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976

В. В. Лидовский. Теория информации. М. Компания Спутник, 2004.