OPISIS_LAB5v2

допустимых кодовых слов. Такой декодер называется полным декодером. С другой стороны, декодер с ограниченным расстоянием исправляет до t ошибок в полученном слове. Если вес ошибки превышает t , это приводит к отказу декодера.

Классификация блочного кода Некоторые из обычно используемых линейных блочных кодов - это коды

Хэмминга, коды Голея, коды БЧХ, коды-повторения, коды Рида-Маллера, коды Рида-Соломона и коды с низкой четностью (LDPC). Блочные коды также подразделяются на две категории, которые различаются по структуре вывода кодера.

Систематическое кодирование

Несистематическое кодирование При систематическом кодировании, просто наблюдая за выходными

данными кодировщика, мы можем разделить данные и избыточные биты (также называемые битами четности). При несистематическом кодировании избыточные биты и биты данных перемежаются (см. рисунок 7).

Рисунок 7 – Систематическое и несистематическое кодирование

Теория линейных блочных кодов

Блочный код C длины n символов с qk кодовыми словами равен называется линейным (n, k) кодом тогда и только тогда, когда его qk кодовых слов образуют k -мерное подпространство векторного пространства всех n-кортежей над полем

GF(q) . Для простейшего случая двоичной передачи q 2 блочный код C длины n-символов с 2k кодовыми словами называется линейным (n, k) кодом тогда и

только тогда, когда его 2k кодовых слов образуют k-мерное подпространство векторное пространство всех наборов из n над полем GF(q) .

Векторное пространство – это набор объектов, которые можно добавлять и умножать с помощью скаляров. Операции, называемые сложением и скалярным умножением, должны подчиняться определенным правилам. Для векторного пространства операция сложения коммутативна и замкнута; скалярное умножение замкнуто, дистрибутивно и ассоциативно. Свойства векторного пространства влияют на кодовые слова блочного кода. Поскольку кодовые слова блочного кода образуют подпространство векторного пространства всех n-кортежей над полем

GF(q) , сумма любых двух кодовых слов в C также является кодовым словом в C ,

а нулевая последовательность также должна быть кодовым словом в C, и,

следовательно, кодовое слово с наименьшим весом дает минимальное расстояние

блочного кода C.

Поскольку мы рассматриваем линейный блочный код, определения основаны на линейном векторном пространстве. В математике набор объектов (или векторов) в векторном пространстве называется базисом, если векторы линейно независимы и каждый вектор в векторном пространстве является линейной комбинацией этого набора. Следовательно, все кодовые слова в C могут быть получены как линейная комбинация базисных векторов. Обозначив базисные

векторы над k-мерным подпространством как операцию

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

Каждый вектор g имеет размерность 1 n . Если m {m0 , m1,..., mk 1} является

последовательностью символов сообщения, вводимых в блочный кодировщик,

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

Теперь мы знаем, что кодовые слова блочного кода образуют k-мерное подпространство векторного пространства всех n-кортежей. Согласно теореме проверки на четность, для каждой порождающей матрицы G существует матрица проверки на четность H, которая охватывает нулевое пространство G.

Следовательно, если c – кодовое слово, то оно будет ортогональным каждой строке

H.

В результате порождающая матрица G (так же называется генераторной матрицей) и матрица проверки на четность H удовлетворяют следующему свойству

Систематическое кодирование – это удобная форма кодирования, при которой исходное сообщение легко идентифицировать по кодовому слову.

Генераторные матрицы могут быть построены таким образом, чтобы результирующее кодирование было в систематической форме. Такие матрицы называются стандартными. Матрицы стандартной формы достигаются путем сокращения строк и переупорядочения столбцов до тех пор, пока не будет выявлена единичная матрица.

Порождающая матрица G в стандартной форме может быть разбита как

где Ik - единичная матрица размера k k , а P имеет размерность k n k . Когда G

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

Следующие функции Matlab преобразуют матрицу генератора стандартной формы в соответствующую матрицу проверки на четность и наоборот.

Программа 2: gen2parmat.m: преобразование матрицы генератора стандартной формы в матрицу проверки на четность

function [H] = gen2parmat(G)

%Convert standard-form binary generator matrix G %into the corresponding parity-check matrix H. [k,n] = size(G);%G is k x n

if k>n, error('G matrix must be of size k x n where k<n'); end I = eye(k); %identity matrix of size k x k

%Find if the G matrix is [P | Ik] or [Ik | P] form, %then form H matrix accordingly

P = G(:,1:n-k); Ik=G(:,n-k+1:n); %Split G like [P | Ik] and test if isequal(Ik,I) %G matrix is of form [P | Ik]

H = [eye(n-k) P.']; else

Ik=G(:,1:k); P = G(:,k+1:n); %Split G like [Ik | P] and test if isequal(Ik,I) %G matrix is of form [Ik | P]

H = [P.' eye(n-k)];

else error('G matrix is not in standard form'); end

end; end

Программа 3: par2genmat.m: преобразовать стандартную матрицу проверки на

четность в генераторную матрицу

function [G] = par2genmat(H)

%Convert standard-form binary parity-check matrix H %into the corresponding generator matrix G.

[r,n] = size(H); %r=n-k : num of parity bits, H matrix is (n-k) x n

k = n-r;

if r>n, error('H matrix must be of size (n-k)xn where (n-k)<n'); end I = eye(n-k); %identity matrix of size (n-k) x (n-k)

%Find if the H matrix is [P' | I(n-k)] or [I(n-k) | P'] form, %then form G matrix accordingly

Pd = H(:,1:k); Ink=H(:,k+1:n); %Split H like [P' | I(n-k)] and test if isequal(Ink,I) %H matrix is of form [P' | I(n-k)]

G = [eye(k) Pd.']; else

Ik=H(:,1:n-k); Pd = H(:,n-k+1:n); %Split H like [I(n-k) | P'] if isequal(Ik,I) %H matrix is of form [Ik | P]

G = [Pd.' eye(k)];

else error('H matrix is not in standard form'); end

end; end

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

G = [1 1 0 1 0 0 0; 0 1 1 0 1 0 0; 1 1 1 0 0 1 0;1 0 1 0 0 0 1]; H = gen2parmat(G)%convert G to H

G = gen2parmat(H)%convert H to G mod(G*H.',2) %to verify GH?T=0

Декодирование с жестким решением линейных блочных кодов для канала с АБГШ Методы декодирования с жестким решением используют метрику расстояния Хэмминга для декодирования принятой последовательности с жестким решением до ближайшего кодового слова. Целью таких методов декодирования является выбор кодового слова, которое обеспечивает минимальное расстояние Хэмминга по отношению к принятой последовательности с жестким решением.

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

Декодирование с использованием стандартного массива и синдромное декодирование - популярные методы декодирования с жесткими решениями,

которые встречаются на практике.

Рисунок 8 – Модель приемника с жестким решением для декодирования линейных блочных кодов для канала AWGN

Декодер по стандартному расположению

Предположим, что кодовое слово c передается по двоичному симметричному каналу (ДСК). Если кодовое слово, передаваемое передатчиком, не искажено шумом, принятый вектор будет таким же, как переданное кодовое слово r c .

Если шум в канале искажает переданное кодовое слово, он вносит шаблон ошибки в полученный вектор. Если c – допустимое кодовое слово, переданное передатчиком, а e – шаблон ошибки, вносимый каналом, то принятый вектор выражается как

(25)

Мы предполагаем, что кодовые слова выбираются декодером с равной вероятностью и что шаблон ошибки с меньшим весом более вероятен, чем шаблон ошибки с более высоким весом. Цель состоит в том, чтобы выбрать кодовое слово c’, наиболее близкое к принятому слову r. То есть мы хотим выбрать вектор ошибки e’ наименьшего веса, удовлетворяющий

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

который эквивалентен декодеру максимального правдоподобия на основе

Созданный стандартный массив можно протестировать, применив его в системе связи, как будет описано далее.

Программа 6: test_standard_array.m: сценарий для проверки декодирования стандартного массива.

%Demonstrate error correction using Standard Array

%Given a generator matrix G, a standard array will be generated. %If r is received vector, the error corrected sequence will be %chosen from the constructed standard array.

clearvars; clc;

G = [0 1 1 1 1 0 0; %Sample Generator matrix to test 1 0 1 1 0 1 0; 1 1 0 1 0 0 1];

[k,n] = size(G); %derive n and k from the G matrix %standard array for the given generator matrix [stdArray] = standardArray(G);

%Randomized simulation to test the communication chain %--------Transmitter with encoder-------------------

x = rand(1,k) > 0.5 %randomized input message to block encoder c = mod(x*G,2) %codeword generated by the block encoder

%randomly select a d-bit error pattern from the matrix of %all d-bit error patterns

index = ceil(rand * size(E,1));

e = E(index,:) %randomly selected error pattern

r = mod(c + e,2) %received vector containing errors %--------Receiver with decoder----------------------

%Search through the standard array for the received vector r

%and return the error term (coset leader) and the codeword %(row header) from standard array.

[row,col]=find(cellfun(@(y) ismember(r, y,'rows'),stdArray)==1); recoveredCW = cell2mat(stdArray(1,col)) %element from the top row errorEst =cell2mat(stdArray(row,1)) %coset leader(estimated error) if (recoveredCW==c), disp('Decoder success');

else, disp('Decoder error'); end

стандартном массиве мы видим, что соответствующий лидер смежного класса - это e 0010000 , а последовательность декодируется как c 1011010 .

Если мы запустим моделирование, чтобы охватить все возможные случаи шаблонов ошибок, мы можем отметить, что данный код (7,3) эффективен для исправления всех одиночных ошибок. Однако исправление шаблонов ошибок с весом два или выше не гарантируется.

Читатель, возможно, заметил очевидную проблему в подходе стандартного расположения для декодирования блочного кода. Простой двоичный блочный код размера n требует, чтобы в памяти было сохранено 2n записей. Если код находится в GF q , ему потребуется место в памяти для qn записей. Требования к памяти быстро возрастают с увеличением количества кодовых слов. В таких случаях могут использоваться альтернативные подходы к декодированию. Один из таких подходов - использовать синдромное декодирование.

Синдромный декодер

Согласно теореме проверки четности, если H является матрицей проверки на четность для кода C, то вектор c в принятом кодовом пространстве является допустимым кодовым словом тогда и только тогда, когда он удовлетворяет условию cH T 0 . Рассмотрим вектор принятого слова r c e , где c - допустимое переданное кодовое слово, а e - ошибка, вносимая каналом. Матричное произведение rH T определяется как синдром для полученного вектора r, который можно рассматривать как линейное преобразование с нулевым пространством C.