OPISIS_LAB5v2

s rH T

(c e)H T

0 eH TeH T

Таким образом, синдром не зависит от переданного кодового слова c и

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

Далее приведена функция Matlab getSyndromeTable для проверки вышеупомянутых моментов. В этой функции мы пытаемся сгенерировать векторы синдромов для всех записей в стандартном массиве, приведенном в таблице 1.

Результат (полученный путем полного перебора S в коде Matlab) представлен в таблице 2. Из этой таблицы мы отмечаем, что синдром одинаков для данной строки и отличается только в случае изменения лидера смежного класса (т. е. изменения строки). Синдромом для всех допустимых кодовых слов являются нули (верхняя строка). Построение таблицы синдромов требует полного перебора и становится невозможным для больших кодов.

Программа 7: getSyndromeTable.m: Построение таблицы синдромов для заданной матрицы генератора

function [syndromeTable] = getSyndromeTable(G)

%function to construct the syndrome table for a given standard_3 %form generator matrix G. Returns a sorted cell array whose

%first column is the syndromes (s=r.H?T) in decimal and the %second column is the estimated error pattern (e').

%G =[0 1 1 1 1 0 0; 1 0 1 1 0 1 0;1 1 0 1 0 0 1];%to test H = gen2parmat(G);%Corresponding parity-check matrix [stdArray] = standardArray(G);%construct standard array A = stdArray; B = H.';

%multiply each element in the standard array with H?T for syndromes S_full = cell(size(A));%for syndromes of all patterns in std array for ii = 1:numel(A)

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

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

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

таблицы синдромов работает эквивалентно стандартному декодеру на основе массива. Однако по сравнению со стандартным декодером массивов подход таблицы синдромов потребляет очень меньше памяти для хранения таблицы поиска.

Таблица 4: Таблица декодирования синдромов для матрицы генератора,

Программа 8: test_syndrome_decoding.m: скрипт для тестирования декодирования с

использованием таблицы синдромов

%Demonstrate error correction using Syndrome table decoding 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 H = gen2parmat(G); %find the H matrix

%Syndrome table for G, index sorted according to syndromes s=rH?T syndromeTable = getSyndromeTable(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 %--------Channel----------------------

d = 1; %d-bit error pattern to test with

%all possible combinations of d-bit error patterns [E,nRows,nCols] = error_pattern_combos(d,n);

%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 syndrome table decoder---------------------

s = mod(r*H.',2) %find the syndrome

s_dec = bi2de(s,'left-msb') %sorted syndomes (first column in table) %read corresponding error pattern from second column errorEst=syndromeTable(s_dec+1,2);%point at index s_dec and return e errorEst = cell2mat(errorEst) %to convert cell to matrix recoveredCW = mod(r - errorEst,2) %recovered codeword

if (recoveredCW==c), disp('Decoder success'); else

disp('Decoder error'); end

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

кратко описаны в этом разделе.

Коды-повторения

Двоичный код с повторением, обозначенный как n,1 код, представляет собой линейный блочный код, имеющий два кодовых слова длины n: кодовое слово, состоящее только из нулей, и кодовое слово из всех единиц. Он имеет

Коды Хэмминга

Линейные двоичные коды Хэмминга подпадают под категорию линейных

блочных кодов, которые могут исправлять однобитовые ошибки. Для каждого

расстояние Хэмминга dmin 3, и, таким образом, они могут исправлять любую одиночную битовую ошибку и обнаруживать любые две битовые ошибки в полученном векторе. Характеристики общего n, k кода Хэмминга приведены

двоичный код Хэмминга. Блочный кодер принимает блоки 4-битной информации,

добавляет 3 бита четности к каждому такому блоку и производит 7-битные блоки,

закодированные по Хэммингу. Коды Хэмминга могут быть реализованы в систематической или несистематической форме. Систематический линейный блочный код может быть преобразован в несистематическую форму преобразованиями элементарных матриц. Далее описывается систематический код

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

P3 D1 D3 D4

На рисунке 9 показан общий процесс вычисления битов четности для кода Хэмминга (7,4).

Рисунок 9 – Вычисление битов четности для (7,4) кода Хэмминга

На стороне передатчика кодер Хэмминга реализует матрицу генератора - G.

Легче построить матрицу генератора из линейных уравнений, перечисленных в

(35). Линейные уравнения показывают, что информационный бит D1 влияет на вычисление четностей в P1 и P3 . Точно так же информационный бит D2 влияет на

P1 и P2 , D3 влияет на P1 , P2 и P3 , а D4 влияет на P2 и P3 .

Кодер принимает 4-битный блок сообщения m, умножает его на порождающую матрицу G и генерирует 7-битовые кодовые слова c. Обратите внимание, что все операции (сложение, умножение и т.д.) Выполняются по модулю

2.

(37)

Учитывая матрицу генератора, ниже дается фрагмент кода Matlab для создания кодовой книги, содержащей все возможные кодовые слова (c C) .

Результирующая кодовая книга C может использоваться в качестве справочной таблицы при реализации кодера. Эта реализация позволит избежать повторного умножения входных блоков и матрицы генератора. Список всех возможных

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

Программа 9: Генерация всех возможных кодовых слов из матрицы генератора

%program to generate all possible codewords for (7,4) Hamming code G=[ 1 0 0 0 1 0 1;

0 1 0 0 1 1 0;

0 0 1 0 1 1 1;

0 0 0 1 0 1 1];%generator matrix - (7,4) Hamming code m=de2bi(0:1:15,'left-msb');%list of all numbers from 0 to 2?k codebook=mod(m*G,2) %list of all possible codewords

Три проверочных уравнения, показанные в уравнении (35), могут быть выражены вместе как матрица проверки на четность - H, которую можно использовать на стороне приемника для обнаружения и исправления ошибок.

Таблица 5: Все возможные кодовые слова для (7,4) кода Хэмминга

Используя функцию gen2parmat, можно проверить матрицу проверки на четность, показанную в уравнении 38. Таблица синдромов для кода Хэмминга может быть построена с помощью функции getSyndromeTable.

Программа 10: Построение матрицы проверки на четность и таблицы синдромов

G=[ 1 0 0 0 1 0 1; %generator matrix for (7,4) Hamming code 0 1 0 0 1 1 0; 0 0 1 0 1 1 1; 0 0 0 1 0 1 1];

H = gen2parmat(G) %find the H matrix

%Syndrome table for G, index sorted according to syndromes s=rH?T syndromeTable = getSyndromeTable(G)

Моделирование производительности декодирования кодов Хэмминга В этом разделе рассматривается производительность по коэффициенту

ошибок по битам системы связи BPSK по каналу AWGN. Теоретическая BER

некодированной системы BPSK берется за основу, с которой сравниваются характеристики двоичной линейной кодированной системы Хэмминга. Для кодированной системы при моделировании учитываются как декодирование с жестким решением, так и декодирование с мягким решением. Выполнено моделирование работы кода Хэмминга (7,4) с порождающей матрицей G (7,4) и

кода Хэмминга (15,11) с порождающей матрицей G (15,11).

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

была использована ранее. Результаты моделирования представлены на рисунке 10.

Программа 11: perf_hamming_bpsk_awgn.m: выполнение мягкого / жесткого

декодирования кодов Хэмминга

%BPSK over AWGN (complex baseband model) with Hamming coding clearvars; clc;

nBits =10^6; %number of source bits

EbN0dB = -2:1:12; % Eb/N0 range in dB for simulation MOD_TYPE='PSK'; %Modulation type

M=2; %For BPSK -> 2-PSK %Block code definitions

G=[ 1 0 0 0 1 1 0; %generator matrix for (7,4) Hamming code 0 1 0 0 1 0 1; 0 0 1 0 0 1 1; 0 0 0 1 1 1 1];

%G =[1 0 0 0 0 0 0 0 0 0 0 0 0 1 1;%G matrix (15,11) Hamming code

%0 1 0 0 0 0 0 0 0 0 0 0 1 0 1;

%0 0 1 0 0 0 0 0 0 0 0 0 1 1 0;

%0 0 0 1 0 0 0 0 0 0 0 0 1 1 1;

%0 0 0 0 1 0 0 0 0 0 0 1 0 0 1;

%0 0 0 0 0 1 0 0 0 0 0 1 0 1 0;

%0 0 0 0 0 0 1 0 0 0 0 1 0 1 1;

%0 0 0 0 0 0 0 1 0 0 0 1 1 0 0;

%0 0 0 0 0 0 0 0 1 0 0 1 1 0 1;

%0 0 0 0 0 0 0 0 0 1 0 1 1 1 0;

%0 0 0 0 0 0 0 0 0 0 1 1 1 1 1];

[k,n] = size(G); %derive n and k from the G matrix H = gen2parmat(G); %find the H matrix

syndromeTable = getSyndromeTable(G); %syndrome table for G m=de2bi(0:1:2^k-1,'left-msb');%list all numbers from 0 to 2^k-1 C=mod(m*G,2); %list of all possible codewords (code book) %EcN0dB calculation to account for overheads

EcN0dB = EbN0dB + 10*log10(log2(M)) + 10*log10(k/n); BER_Hamming_Hard = zeros(1,length(EbN0dB));%simulated BER (Hard)

for i=1:length(EcN0dB)

%---- Transmitter - Block encoding, BPSK modulation-------

x =rand(1,nBits) > 0.5; %stream of random information bits %append zeros to account for block size of encoder

x =[x zeros(1,k-mod(nBits,k))]; %reshape information stream to blocks

m = reshape(x,k,length(x)/k).'; %message blocks

cBlocks = mod(m*G,2);%codewords generated by the block encoder c= cBlocks.'; c = c(:).';%serialize codewords into one stream y = 2*c-1;%BPSK modulation

%---------AWGN channel --------------------

r = add_awgn_noise(y,EcN0dB(i));%add AWGN noise

%--------Hard decision decoding---------

rHard = (r>=0);%BPSK demodulation (Hard) rHardBlks=reshape(rHard,n,length(rHard)/n).';%blocks of length n syndrome = mod(rHardBlks*H.',2); %find the syndrome

syndrome = bi2de(syndrome,'left-msb');%decimal for indexing %1st column in syndrome table is syndrome, 2nd column is error errorEst=cell2mat(syndromeTable(syndrome+1,2));%return errors cHardBlks = mod(rHardBlks-errorEst,2);%recovered codewords mHardBlks = cHardBlks(:,1:k);%strip off parity bits