Синтез кодека кода Хэмминга

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

Раздел 1. Введение

Раздел 2. Выбор и обоснование параметров входа

Раздел 3. Разработка кодека

3.1 Синтез кодера

3.2 Синтез декодера

Раздел 4. Заключение

Список использованной литературы

Раздел 1. Введение

парафазный кодек декодер

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

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

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

В данном случае параметр n - длина кодового слова. При этом не все разряды этого слова являются информационными. Число информационных разрядов обозначается как k. Оставшиеся n-k разрядов называются проверочными и обозначаются буквой r.

Линейные коды задаются с помощью проверочной Н и порождающей G матриц. Эти матрицы связаны основным уравнением кодирования:

G•HT = 0.

Все кодовые слова линейного кода образуют некоторое векторное пространство, базисом которого являются строки матрицы G. Так как линейно независимые векторы можно выбрать произвольно, то можно построить множество различных матриц G с одним и тем же кодовым расстоянием. Такие матрицы называются эквивалентными. Такие коды различаются различными проверочными символами при одинаковых информационных. С точки зрения алгебры, в проверочной матрице можно переставлять местами строки и столбцы и заменять i-ю строку на сумму i-й и j-й. Применяя эти операции можно привести матрицу G к приведено-ступенчатому виду:

,

где Ik - единичная матрица размерности k.

Таким образом, проверочная матрица будет иметь вид

Имея порождающую матрицу такого вида, для кодирования информационного слова А размерности k необходимо умножить вектор-строку А на порождающую матрицу G:

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

В данном проекте используется код Хэмминга. Он является линейным и обычно задается проверочной матрицей. Она должна быть записана в приведено-ступенчатом виде. Тогда по этой матрице составляются уравнения, суммируя построчно те элементы, значения которых равны единице и приравняв эту сумму нулю. В правую часть каждого уравнения перенесем последний элемент. Таким образом, получим систему из r уравнений, которая вычисляет r проверочных символов. Эти символы добавляются к информационным и используются для обнаружения и коррекции ошибок при передаче, хранении или обработке информации. Это и есть процесс кодирования.

Декодирование осуществляется двумя методами - синдромным или мажоритарным. В проекте использован именно синдромный метод. В этом случае устройство декодирования в блоке вычисления синдрома вычисляет синдром и передает его на блок селекции ошибки, который, по сути, является дешифратором. Дешифратор выдает вектор, в единственной позиции которого единица, а в остальных - нули. Этот вектор называется вектором ошибки. Далее этот вектор поразрядно суммируется по модулю 2 с принятым сигналом. Таким образом, мы получаем исправленное информационное слово. В случае, когда синдром равен нулю, ошибки при передаче не произошло.

В проекте использована разновидность модифицированного кода Хэмминга - укороченный код Хэмминга. Обычный код задается параметрами (n;k) = (2m - 1;2m - m - 1).

В случае, когда k должно быть меньше, чем (2m-m-1), из полной проверочной матрицы необходимо исключить нужное количество столбцов, вес которых больше единицы, получив тем самым требуемое число информационных позиций при той же корректирующей способности. На практике предпочтительно исключать столбцы с наибольшим весом, так как это уменьшает число сумматоров по модулю два в кодирующей и декодирующей схемах.

Далее рассматривается синтез кодека Хэмминга с конкретными параметрами и его реализация на ИС.

Раздел 2. Выбор и обоснование параметров входа

Кодовое расстояние заданного кода равно d=3. Таким образом, исходя из соотношений

d = 2•tи + 1

d = tоб + 1

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

Так как код является двоичным, то основание кода равно q={0;1}.

Число информационных позиций равно k=22 . Такое число позиций не стандартно для кода Хэмминга, поэтому будем использовать код (31,26), укоротив его на T разрядов:

T = k0 - k =26 - 22 = 4 .

Тогда длина кода n будет следующей:

n = n0 - T = 31 - 4 = 27 .

Число проверочных позиций r в данном коде будет равно:

r = n - k = 27 - 22 = 5 .

Таким образом, заданный код будет являться кодом (27,22).

Раздел 3. Разработка кодека

3.1 Синтез кодера.

Для реализации кодера составим проверочную матрицу Н. Для этого будем использовать образующий полином степени r :

x5 + x2 + 1

Так как используемый код является укороченным кодом Хэмминга, то сначала необходимо составить проверочную матрицу полного кода (31,26). Она будет иметь следующий вид:

Затем исключим произвольные столбцы весом больше единицы (w>1). Количество исключенных столбцов равно Т. Для удобства и упрощения вычислений будем выбирать столбцы с максимальным весом. Таким образом, требуемая проверочная матрица Н будет следующая:

Из матрицы Н составляем уравнения, которые, собственно, и реализует кодер при вычислении проверочных разрядов. Уравнения составляются методом сложения элементов построчно по модулю 2:

Синтез функциональной схемы кодера.

Требуемые двоичные сумматоры по модулю 2 реализуем используя схему проверки четности. Таким образом, в схеме используется 5 сумматоров для вычисления проверочных разрядов. Данная схема кодера использует параллельный интерфейс ввода и вывода данных. Выходы сумматоров выводятся параллельно информационным выходам, получая 22 входа и 27 выходов.

Функциональная схема кодера представлена на рисунке 3.1 .

Рисунок 1. Функциональная схема кодера кода Хэмминга (27,22).

Синтез принципиальной схемы.

Схему кодера реализуем на ИС серии КР1554 (КМОП). Для этого необходимо построить двенадцатиразрядную схему контроля чётности. Наибольшее число входов имеет девятиразрядная схема контроля чётности КР1554ИП5. Тогда, используя две таких ИС, составим требуемый логический модуль:

Рисунок 2. Двенадцатиразрядная схема контроля чётности на элементах серии КР1554

Задержка микросхемы КР1554ИП5 составляет 2,23 нс. Тогда общая задержка кодера 4,38 нс. Такие показатели удовлетворяют заданному условию.

3.2 Синтез декодера

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

· В соответствии с входным сигналом и исходными уравнениями кодирования, вычисляется синдром. Этот блок декодера называется блоком вычисления синдрома. Если вычисленный синдром равен нулю, то в данном случае ошибки при передаче не произошло.

· Если синдром нулю не равен, то необходимо установить в каком именно разряде произошла ошибка. Как уже говорилось выше, данная схема кодека способна исправить только одиночную ошибку. Синдром поступает на селектор ошибки, который представляет собой неполный дешифратор, построенный на основе проверочной таблицы Н. То есть, если синдром равен значению i-го столбца, то именно в i-том разряде кода произошла ошибка. В результате формируется вектор ошибки Е, который содержит все нули кроме разряда, в котором произошла ошибка.

· Далее в корректоре исходный сигнал исправляется в соответствии с вектором ошибки. Корректор осуществляет операцию сложения по модулю 2 поразрядно. Исправлять ошибку имеет смысл только в информационных разрядах.

· Исправленный код подается на выход устройства.

Рисунок 3. Структурная схема синдромного декодера кода Хэмминга.

Синтез функциональной схемы декодера.

Функционирование декодера также будет осуществляться по параллельному интерфейсу.

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

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

Корректор построим на двоичных двухвходовых сумматорах по модулю 2, поразрядно подавая соответствующие позиции принятого сообщения и вектора ошибки, полученного в селекторе.

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

Функциональная схема декодера показана на рисунке 4.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Синтез принципиальной схемы декодера.

Схему декодера также реализуем на ИС серии КР1554.

Как и в схеме кодера, тринадцатиразрядную схему контроля четности для БВС построим используя КР1554ИП5, задействовав еще один вход на втором элементе. Задержка этой ИС составляет также 4,38 нс.

Рисунок 5. Тринадцатиразрядная схема контроля чётности на элементах серии КР1554

Требуемый для реализации селектора парафазный буфер построим на микросхеме КР1554ЛН1, которая представляет собой 6 элементов НЕ, подавая прямые значения синдрома параллельно инверсным. Далее селектор использует 22 элемента 5И. В данной серии максимальное число входов элементов И - 4. Поэтому будем использовать последовательно соединенные 4И и 2И. Для этого используем микросхемы КР1554ЛИ1 - 4 логических элемента 2И, и КР1554ЛИ6 - 2 логических элемента 4И. Эти микросхемы соединим по способу, указанному на рисунке 5. Задержка данной схемы составляет 2,76 нс.

Рисунок 6. 4 логических элемента 5И на элементах серии КР1554.

При построении корректора вместо двоичных сумматоров по модулю 2 используем логический элемент Исключающее ИЛИ, а конкретно микросхему КР1554ЛП5 - 4 двухвходовых элемента Исключающее ИЛИ.

После корректора выводы подаются на выход схемы.

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

· КР1554ИП5 - девятиразрядная схема контроля четности.

· КР1554ЛП5 - 4 двухвходовых логических элемента Исключающее ИЛИ.

· КР1554ЛИ1 - 4 логических элемента 2И.

· КР1554ЛИ6 - 2 логических элемента 4И.

· КР1554ЛН1 - 6 логических элементов НЕ.

Используя данную серию микросхем, получим общую задержку 7,54 нс. Такой результат вполне удовлетворяет поставленной задаче. Для расчета задержек была использована программа Altera Max +Plus II.

Раздел 4. Заключение

В процессе выполнения курсового проекта был синтезирован кодек кода Хэмминга (27,22). Такой код является укороченным кодом Хэмминга. Декодирование осуществляется синдромным методом. Данный код позволяет обнаружить двойную и исправить одиночную ошибку при передаче по каналу связи или при хранении данных. Кодер и декодер используют параллельный интерфейс ввода и вывода данных. При аппаратной реализации была использована серия интегральных схем КР1554.

Список использованной литературы

1. «Теория прикладного кодирования» в двух томах под редакцией проф. В.К. Конопелько, Минск БГУИР, 2004г.

2. «Интегральные микросхемы и их зарубежные аналоги» справочник А.В. Нефедов, Радиософт,2009г.

Размещено на Allbest.ru