Разработка системы защиты от ошибок в сетях передачи данных

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

         Для обеспечения этих условий  составим уравнения проверок (2.6) таким образом, чтобы все они содержали по три слагаемых, не повторяя друг друга:

Эти условия позволяют построить  на основании информационной подматрицы построить проверочную, а с ней – и производящую:

Таким образом, первые четыре разрешенные  кодовые комбинации получаются непосредственно из производящей матрицы: U⁽¹⁾ = {1000110}; U⁽²⁾ = {1100011}; U⁽³⁾ = {1110100}; U⁽⁴⁾ = {1111111}.

Всего разрешенных комбинаций Sр = 24 = 16, одна из которых тривиальна U(16) = {0000000}. Остальные 11 кодов можно получить, комбинируя базисные:

U(5)=U(1)) U(2);U(6)=U(1) U(3);U(7)=U(1)) U(4);U(8)=U(2) U(3); 
U(9)=U(2) U(4);U(10))=U(3) U(4);U(11)=U(1) U(2) U(3); 
U(11)=U(1) U(2) U(3);U(12)=U(1) U(2) U(4); 
U(13)=U(1) U(3) U(4);U(14)=U(2) U(3) U(4); 
U(15) = U(1) U(2) U(3) U(4).

Легко проверить корректирующие свойства построенных кодов: пусть вместо U⁽⁵⁾ = {0100101} получена комбинация (U⁽⁵⁾)' = {0110101}, т.е. в третьем бите возникла ошибка. На основании условий проверок получаем:

(p1)'=0 1 1=0#p1, т.е. ошибка в u1 или u2, или u3, но не u4. 
(p2)'=0 1 0=1#p2, т.е. ошибка в u1 или u3, но не u2. 
(p3)'=1 1 0=0# p3, т.е. ошибка в u3.

После локализации ошибки достаточно инвертировать  ошибочный бит (т.е. заменить 1 на 0 или 0 на 1).

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

 

 

2.2. Кодер и декодер систематического  кода

 

         При использовании помехоустойчивых  и, в частности, систематических  кодов кодирование знаков первичного алфавита осуществляется в два этапа. На начальном этапе знаки первичного алфавита от источника поступают в первичный кодер – устройство, производящее кодирование по заданной схеме без учета возможных искажений, т.е. формируется только информационная часть кода. Далее вторичный кодер добавляет к ней проверочные знаки и формирует разрешенные помехоустойчивые кодовые комбинации. Ситуация иллюстрируется рисунке 1.5 – показана схема кодера для рассмотренного выше (7,4)-кода.

 

Рисунок 2.7 Схема кодера систематического кода

         Логика декодирования основывается  на сравнении значений проверочных  бит, составленных по принятой  кодовой комбинации (обозначим их p_j'' ), с непосредственно принятыми проверочными битами (p_j' ). В результате сравнения формируются новые проверочные биты (q_j) по следующему правилу:

; (1.1)

где u_i – принятые информационные биты кода.

     Совокупность q_j образует новый кодовый вектор Q = {q₁,… q_r}, который получил название синдрома ошибок. Значение «0» в любой позиции Q свидетельствует об отсутствии ошибки в бите кода, связанного с этой позицией; если синдром весь состоит из нулей («нулевой синдром»), то это означает, что вся кодовая комбинация передана безошибочно; присутствие одной или нескольких «1» говорит о наличии ошибок передачи. При этом каждому ненулевому синдрому однозначно соответствует ошибка в определенном бите принятой кодовой комбинации. Все ненулевые синдромы заносятся в таблицу – она называется таблицей исправлений, которая и определяет алгоритм работы декодера. Общее число ненулевых синдромов, очевидно, равно 2^r – 1; из них для проверки требуется n, а для исправления только k.

       Составим таблицу исправлений  для рассмотренного в предыдущем  пункте (7,4)-кода и условий проверки (2.7).

     Предположим, ошибочно передан  бит u₁, а все остальные знаки кода переданы верно. Это повлечет отличие (несовпадение) тех проверочных бит p_j' и p_j'' , в которые входит u₁ – это p₁ и p₂; соот-ветственно, значения q_j окажутся равными: q₁ = 1, q₂ = 1 и q₃= 0. Таким образом, ошибке в u₁ соответствует синдром Q = {110}. Ошибке в проверочном бите, например, p₃, будет отвечать синдром Q = {001}. Продолжив аналогичные рассуждения, получим полную таблицу исправлений (таблица 2.3):

 

Таблица 1.

 

Непосредственно исправление ошибочного бита производит блок декодера называемый дешифратором: если синдром указывает на ошибку в одном из проверочных бит, исправлений в информационных битах не требуется и дешифратор выдает «0» на все выходы; если синдром указывает на ошибку в каком-либо информационном бите, дешифратор посылает «1» на вход сумматора по mod 2 именно этого бита, в результате чего бит инвертируется и ошибка исправляется. Схема декодера систематического кода представлена на рис.

Рисунок Схема декодера систематического кода

 

 

 

       

 

2.3 Каноническая форма систематических  кодов

            Корректирующие качества (n,k) кода определяются минимальным кодовым расстоянием, равным наименьшему весу всех базовых комбинаций, который, в свою очередь, определяется числом проверочных бит r. Следовательно, все систематические коды с одними и теми же n и k, хотя они имеют различные порождающие матрицы, но обладают одинаковыми свойствами по обнаружению и исправлению ошибок. Это позволяет из всех порождающих матриц выделить какую-либо одну, например, из соображений удобства и простоты построения кодов и их декодирования на приеме. Такому условию удовлетворяет так называемая каноническая форма производящей матрицы.

         Для представления производящей  матрицы в канонической форме  необходимо ее информационную часть A_k,k составить из векторов-ортов k-мерного пространства:

(1)

    Другими словами, информационная  часть представляет собой единичную  диагональную матрицу.

     Порядок построения проверочной  подматрицы P_r,k рассмотрим на примере кода (7,4). Поскольку r = 3, проверочная подматрица будет содержать 3 столбца и 4 строки; чтобы код исправлял однократные ошибки, необходимо d_min = 3, т.е. в каждой строке P_3,4 должно содержаться не менее двух единичных бит (один уже имеется в информационной части), причем, все комбинации должны различаться. Достаточно очевидно, что при k = 4 таких комбинаций всего четыре (порядок их следования значения не имеет):

(2)_

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

(3)

Для получения правил проверок нужно  каждую строку (i) порождающей матрицы домножить на u_i и произвести суммирование в столбцах:

(4)

Получаем:

  (5)

 

  Дадим ряд вспомогательных определений.

Два кодовых вектора называются ортогональными, если их скалярное произведение равно 0, т.е. для двух векторов одинаковой длины U = {u₁…u_n} и V = {v₁…v_n} выполняется соотношение (при суммировании по mod 2):

(6)

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

Для иллюстрации дальнейший рассуждений  вновь обратимся к коду (7,4). Найдем вектор V, ортогональный всем четырем базисным:

(U1·V)=u1v1 u5v5 u6v6=v1 v5 v6=0 v1=v5 v6 
(U2·V)=u2v2 u5v5 u7v7=v2 v5 v7=0 v2=v5 v7 
(U3·V)=u3v3 u6v6 u7v7=v3 v6 v7=0 v3=v6 v7 
(U4·V)= u4 v4 u5 v5 u6 v6 u7 v7 = v4 v5 v6 v7= 0

v4 = v5 v6 v7

    В результате мы получаем систему  условий, позволяющих найти v₁ v₄ по заданным v₅ v₇. Всего ортогональный векторов должно быть 3 (поскольку r = 3); для их построения можно выбрать v₅ v₇ удобным образом, а v₁ v₄ рассчитать по полученным ранее соотношениям; наиболее простым будет такой выбор v₅ v₇, чтобы в каждом из трех вариантов лишь одно из значений было бы равно 1, а остальные – 0. Получившиеся таким образом комбинации образуют новую матрицу H_n,r:

Эта матрица называется проверочной. Основания  к этому следующие.

Во-первых, видно, что элементы в каждой строке матрицы в колонках с первой по четвертую совпадают с полученными ранее условиями проверки (2.18).

Прежде  чем сказать «во-вторых», выявим связь Gn,k и Hn,r.

Видно, что H_n–r,r = P_r,k^T , где P_r,k^T – транспонированная проверочная подматрица.

Транспонированной называется матрица, строки которой являются столбцами, а столбцы – строками исходной матрицы.

Для рассматриваемой канонической G_7,4

что совпадает с H_7-3,3. Таким образом, становится ясным правило построения проверочной матрицы:

H_n,r = P_r,k^T + E_r,r

где E_r,r – единичная диагональная матрица r×r.

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

произведение  принятой кодовой комбинации на строки проверочной дает синдром        
Q = U^' × H_n,r^T

Пусть U₅=U₁×U₂= {1110011}, а при приеме получена комбинация U₅^'= {1110011}, т.е. ошибочным является 3-й бит.

что совпадает с третьим столбцом проверочной матрицы и соответствует 3-му информационному биту.

Таким образом, на основании проведенного рассмотрения можно сделать следующие  выводы:

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

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

Все операции проверки алгоритмизируются  и, следовательно, могут выполняться устройством.

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

                                          2^r – r =1 + k,(6)

                       где r-число контрольных битов.

                              k-число информационных битов.

В данном случае число контрольных битов равно пяти.

В таком случае окончательно постановка задачи для программы примет вид: закодировать n,k-код (31,26) пятью проверочными. 

 

 

 2.3.1.Обоснование выбора микроконтроллера 16F84.

 

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

       Описание контроллера PIC16F84

        PIC16F84 относится к семейству КМОП микроконтроллеров. Отличается  тем, что имеет внутреннее 1K x 14 бит EEPROM для программ,  8-битовые данные  и 64байт EEPROM памяти  данных.Пользователи,  которые  знакомы  с  семейством PIC16C5X могут посмотреть подробный список отличий нового  от  производимых ранее контроллеров. Все команды состоят из одного слова (14 бит шириной)  и исполняются за один цикл (1  мкс  при  4  МГц),  кроме  команд  перехода, которые выполняются за два  цикла  (2 мкс).  PIC16F84  имеет прерывание, срабатывающее от четырех источников,  и восьмиуровневый аппаратный  стек. Периферия   включает   в   себя   8-битный   таймер/счетчик   с    8-битным программируемым предварительным делителем (фактически 16 - битный таймер) и 13 линий двунаправленного ввода/вывода. Разработки   на   базе   контроллеров   PIC16F84   поддерживается ассемблером,  программным  симулятором,  внутрисхемным  эмулятором  (только фирмы Microchiр) и программатором.