Табл.1.1 -- Размерность кода

Этого теоретического нижнего предела можно достичь, используя метод Ричарда Хэмминга. В коде Хэмминга к слову, состоящему из m битов, добавляется r битов четности, при этом образуется слово длиной m+r битов. Биты нумеруются с единицы (а не с нуля), причем первым считается крайний левый. Все биты, номера которых -- степени двойки, являются битами четности; остальные используются для данных. Например, к 16-битному слову нужно добавить 5 битов четности. Биты с номерами 1, 2, 4, 8 и 16 -- биты четности, а все остальные -- биты данных. Всего слово содержит 21 бит (16 битов данных и 5 битов четности). В рассматриваемом примере будем использовать положительную четность (выбор произвольный). Каждый бит четности проверяет определенные битовые позиции. Общее число битов со значением 1 в проверяемых позициях должно быть четным. Ниже указаны позиции проверки для каждого бита четности:

Бит 1 проверяет биты 1,3,5,7,9,11,13,15,17,19,21.

Бит 2 проверяет биты 2,3,6,7,10, 11, 14,15,18,19.

Бит 4 проверяет биты 4,5,6,7,12,13,14,15,20,21.

Бит 8 проверяет биты 8,9, 10, 11,12,13,14,15.

Бит 16 проверяет биты 16,17,18,19,20,21.

В общем случае бит b проверяется битами b1, b2,..., bj, такими что b1+b2+...+bj=b.

Например, бит 5 проверяется битами 1 и 4, поскольку 1+4-5. Бит 6 проверяется битами 2 и 4, поскольку 2+4=6 и т. д.

На рис. 1.3 показано построение кода Хэмминга для 16-битного слова 1111000010101110. Соответствующим 21-битным кодированным словом является 001011 100000101101110. Чтобы увидеть, как происходит исправление ошибок, рассмотрим, что произойдет, если бит 5 изменит значение из-за резкого скачка напряжения на линии электропередачи. В результате вместо кодированного слова 001011100000101101110 получится 001001100000101101110. Будут проверены 5 битов четности. Вот результаты проверки:

Бит четности 1 неправильный (биты 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 содержат пять единиц).

Бит четности 2 правильный (биты 2,3,6,7,10,11,14,15,18,19 содержат шесть единиц).

Бит четности 4 неправильный (биты 4,5,6,7,12,13,14,15,20,21 содержат пять единиц).

Бит четности 8 правильный (биты 8,9,10,11,12,13,14,15 содержат две единицы).

Бит четности 16 правильный (биты 16,17,18,19,20,21 содержат четыре единицы).

Общее число единиц в битах 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 и 21 должно быть четным, поскольку в данном случае используется положительная четность. Неправильным должен быть один из битов, проверяемых битом четности 1 (а именно 1,3,5,7,9,11,13,15,17,19 и 21). Бит четности 4 тоже неправильный. Это значит, что изменил значение один из следующих битов: 4,5,6,7,12,13,14,15,20,21. Ошибка должна быть в бите, который содержится в обоих списках. В данном случае общими являются биты 5,7,13,15 и 21. Поскольку бит четности 2 правильный, биты 7 и 15 исключаются. Правильность бита четности 8 исключает наличие ошибки в бите 13. Наконец, бит 21 также исключается, поскольку бит четности 16 правильный. В итоге остается бит 5, в котором и содержится ошибка. Поскольку этот бит имеет значение 1, он должен принять значение 0. Именно таким образом исправляются ошибки.

Рис. 1.3 -- Построение кода Хэмминга для слова 1111000010101110с помощью добавления 5 контрольных разрядов к битам данных

Чтобы найти неправильный бит, сначала нужно подсчитать все биты четности. Если они правильные, ошибки нет (или есть, но больше одной). Если обнаружились неправильные биты четности, то нужно сложить их номера. Сумма, полученная в результате, даст номер позиции неправильного бита. Например, если биты четности 1 и 4 неправильные, а 2, 8 и 16 правильные, то ошибка произошла в бите 5 (1+4)

1.4 Код Рида - Соломона

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

для трёх единиц информации (байт):байт1 + байт2 + байт3 + X + Y = 0

байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y = 0

для расчета конкретных значений X и Y для кодирования трёх байт:

Y = 3 * байт1 + 2 * байт2 + байт3X = -4 * байт1 - 3 * байт2 - 2 * байт3

Теперь для выяснения ошибки и её коррекции применяем следующие расчеты:

Значение_ошибки = байт1 + байт2 + байт3 + X + Y

Так как ранее (до возникновения ошибки) эта сумма была равна 0, то теперь она равна непосредственно значению ошибки, которое достаточно просто вычесть из недоброкачественного байта. В случае если блок принят безошибочно, то Значение_ошибки = 0. Теперь найдём байт который надо исправлять:

N = байт1 + 2 * байт2 + 3 * байт3 + 4 * X + 5 * Y

Номер_ ошибочного_ байта = N / Значение_ ошибки

При реализации этого в реальный алгоритм необходимо обязательно осуществлять проверку на то существует ошибка в блоке или нет, то есть Значение_ошибки = 0 или нет, иначе получаем деление на ноль.

Если необходимо защитить кодом Рида-Соломона блок данных более 3х байт, то формулы расчета корректирующих значений лишь немного изменяются (для 16 байт):

Y = 16 * байт1 + 15 * байт2 + 14 * байт3 + ... + байт16X = -17 * байт1 - 16 * *байт2 - 15 * байт3 - ... - 2 * байт16

Значение_ошибки = байт1 + байт2 + байт3 + ... + X + YN = байт1 + 2 * *байт2 + 3 * байт3 + ... + 16 * байт16 + 17 * X + 18 * Y

Данным кодом неудобно защищать блоки информации менее 4 байт, так как длинна контрольных параметров X и Y должна быть как минимум 4 байта

2 байта (DW) для X и 2 байта на Y, то есть получается. что к блоку данных из 4 байт будет добавлен корректирующий блок из 4 байт.

Но что делать, если возникло две или более ошибок в блоке ?

Как один из признаков возникновения двух ошибок можно считать получения в качестве номер ошибочного байта дробного числа, например если в блоке из нулей встретится 2 единицы (две ошибки), в третьем и четвёртом байтах, то Номер ошибочного байта = 3.5 но если 4 единицы, соответственно в 3, 4 и 5 байтах то Номер ошибочного байта = 4.

2 Разработка стенда контроля передаваемой информации

Для визуализации процесса помехоустойчивого кодирования можно разработать устройство, которое поможет понять принцип работы метода Хэмминга. Кодер - декодер будем разрабатывать на основе ИМС К555ВЖ1.

2.1 Разработка устройства кодирования информации методом Хемминга

Кодер, преобразует 32х битное слово в 38ми разрядный код Хэмминга, после чего слово хранится в памяти или передаётся по шинам и т.д. В процессе передачи или хранения в слове может произойти ошибка, поэтому декодер не просто декодирует слово, но и исправляет единичные ошибки. Процесс кодирования и декодирования можно представить в виде блок-схемы приведенной ниже.

Рис. 2.1 блок схема кодирования

Рис. 2.2 -- Схема кодера

На входы а1,а2…а32 подаётся кодируемое слово. Блоки (элементы) KR1, KR2, KR4, KR8, KR16 и KR32 формируют контрольные разряды (биты чётности). Весь процесс кодирования сводится к формированию контрольных разрядов и сдвигу имеющихся разрядов. Так, 1й бит слова становится 3м битом кода, а 2й - 5м , 1,2,4,8,16,32 биты - контрольные. В результате кодирования 32х битное слово становится 38ми битным.

Рис 2.3 -- Схема блоков KR1 - KR32

Блоки KR1, KR2, KR4, KR8, KR16 и KR32 собраны элементах исключающее ИЛИ. Итак:

Блок KR1 формирует 1й контрольный разряд подсчитывая чётность 3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35 и 37 битов, если количество единиц в этих разрядах чётное, то контрольный бит равен нулю, если нечётное - единица.

Аналогично блок KR2 формирует 2й контрольный разряд, подсчитывая чётность 3,6,7,10,11,14,15,18,19,22,23,26,27,30,31,34,35 и 38 битов, если количество единиц в этих разрядах чётное, то контрольный бит равен нулю, если нечётное - единица.

Блок KR4 формирует 4й контрольный бит проверяя 5,6,7,12,13,14,15,20,21,22,23,28,29,30,31,36,37 и 38 биты.

Блок KR8 формирует 8й контрольный бит проверяя 9,10,11,12,13,14,15,24,25,26,27,28,29,30 и 31 биты.

Блок KR16 формирует 16й контрольный бит проверяя 17,18,19,20,21,22,23,24,25,26,27,28,29,30 и 31 биты.

Блок KR32 формирует 32й контрольный бит проверяя 33,34,35,36,37 и 38 биты.

2.2 Разработка устройства декодирования информации методом Хемминга

Рис.2.4 -- Схема декодера

Схема декодера состоит из 3х основных блоков: блока анализа, блока управления и блока исправления. Декодер осуществляет декодирование с исправлением произошедшей ошибки.

Рис. 2.5 -- Схема блока анализа

Блок анализа с помощью блоков KR1, KR2, KR4, KR8, KR16 и KR32 заново проверяет чётность выше упомянутых разрядов и с помощью 6 и элементов исключающее ИЛИ сравнивает с пришедшими по шине контрольными разрядами. Если контрольные разряды нарушены, то формируются 6 сигналов ошибки, которые передаются в блок управления. Так же блок анализа изымает из 38ми битного слова биты чётности и передаёт 32х битное слово в блок исправления.

Рис. 2.6 -- Схема блока управления

Блок управления представляет дешифратор 6/32, собранный на базе элементов И. В соответствии с комбинацией входных сигналов, блок управления активирует тот или иной управляемый инвертор блока исправления.

Рис 2.7 -- Схема блока исправления ошибок

Блок исправления непосредственно производит исправление слова пришедшего из блока анализа в соответствии с сигналами блока управления. Он представляет собой 32 управляемых инвертора, на информационные входы которых подаётся слово с ошибкой, а на управляющие код из блока управления. В соответствии с поданным сигналом активируется тот или иной инвертор, который и исправляет ошибку, и слово выводится из дешифратора.

Рис.2.8 -- Схема управляемого инвертора

Управляемый инвертор собран на базе 2х элементов НЕ, элемента И, и элемента исключающее ИЛИ-НЕ. Является непосредственно исполнителем исправления ошибки. Его таблица истинности приведена ниже.

Табл. 2.1 -- таблица истинности управляемого инвертора

2.3 Реализация кодера - декодера на базе ИМС К555ВЖ1

Рис 2.9 -- Блок схема

32х битное слово разделяется на два слова по 16 бит. Далее каждая из половин попадает в свой 16битный кодер. Генерируются контрольные биты, и на линию передач выводятся два 22х битных кода Хэмминга. На линии передачи есть возможность внести ошибку. Далее 22х битный код считывается декодером. Проверяется на наличие ошибок. Если найдены ошибки, они исправляются, и выводятся два слова по 16 бит, которые и составляют переданное 32х битное слово.

2.3.1 Цоколёвка ИМС К555ВЖ1 (SN74LS630)

Рис. 2.10 -- Цоколёвка ИМС К555ВЖ1 (SN74LS630)

· D0-D15 - входы/выходы данных;

· CB0-CB5 - входы/выходы синдрома;

· S0,S1 - входы управления;

· SEF - флаг ошибки;

· DEF - флаг некорректируемой ошибки.

· Все выходы с тремя состояниями

Схема использует модифицированный код Хэмминга, чтобы генерировать 6-битовый синдром для 16-разрядного слова. Одиночные ошибки схемой исправляются; двойные ошибки только обнаруживаются, ошибки типа всех нулей или всех единиц тоже обнаруживаются, тройные и большие ошибки могут быть не обнаружены. В случае двойной ошибки, оба бита могут быть в слове памяти, обе в слове синдрома, или по одному биту в слове памяти и слове синдрома. В течении цикла записи, схема формирует 6-разрядное проверочное слово из 16-разрядного слова данных. Коррекция ошибки выполняется идентификацией неправильного бита и инверсией его. Когда исправленное слово выдается из порта данных, из порта CBi выдается синдром, указывающий на неправильный бит.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8