Министерство образования РеспубликиБеларусь
Белорусскийгосударственный университет
информатикии радиоэлектроники
Кафедра метрологии и стандартизацииК защите допускаю
"__" 2009г.
преподаватель Гурский А.Л.
Пояснительная записка
к курсовой работе на тему:
" Преобразование параллельногодвоичного
кода в код Хэмминга "
Выполнила: Проверил:
ст. группы 762101 Гурский А.Л.
Лазарева Е.О.
Минск 2009
Преобразователь кодов(кодопреобразователь) – логическая схема, которая изменяет данные,представленные в одном двоичном виде, в другой вид, также двоичный. Наиболеечасто используемые кодопреобразователи: двоично-десятичный код всемисегментный; двоично-десятичный код в двоичный; двоичный код вдвоично-десятичный; двоичный код в код Грея; двоичный код в код Хэмминга;двоичный код в код Айкена.
Преобразователи кодов (ПК) могут бытьвесовыми и невесовыми. Весовые ПК преобразуют информацию из одной системысчисления в другую. Основное назначение невесовых — преобразование информациидля ее дальнейшего отображения.
Информация в цифровых устройствахможет быть представлена в последовательном и параллельном кодах. При использованиипоследовательного кода каждый такт соответствует одному разряду двоичного кода.Номер разряда определяется номером такта, отсчитываемого от такта, совпадающегос началом представления кода. Параллельный код позволяет существенно сократитьвремя обработки и передачи информации.
Цифровые устройства по характеруинформации на входах и выходах подразделяют на устройства последовательного,параллельного и смешанного действия. В последних, например, входное слово можетпредставляется в параллельной форме, а выходное — в последовательной.
В данной работе используетсяпреобразователь параллельного двоичного кода в код Хэмминга, который являетсяпомехоустойчивым. Помехоустойчивое кодирование основано на введенииопределенным образом избыточной информации в передаваемые сообщения.Помехоустойчивыми называются коды, позволяющие обнаруживать и (или) исправлятьошибки в кодовых словах, которые возникают при передаче по каналам связи.Преднамеренное введение избыточной информации в передаваемые информационные сообщенияобеспечивает возможность обнаружения по определенным алгоритмам и коррекцииошибочных информационных символов.
В настоящее время помехоустойчивоекодирование широко используется во многих областях техники: в системахобработки информации, в устройствах памяти ЭВМ, в системах записи на магнитныеленты, компакт-диски, в системах управления ракетами, сжатия информации и т.д. Таким образом, помехоустойчивоекодирование играет немаловажную роль в процессе передачи и хранения информации.
1. ОСНОВНЫЕ СВЕДЕНИЯ О ПРИНЦИПАХ ПОСТРОЕНИЯ КОДОВ ХЭММИНГА
В курсовом проекте для графическогоизображения кодера кода Хэмминга используются три основных вида схем:
— структурная схема;
— функциональная схема;
— принципиальная схема.
Различаются они своим назначением и степеньюдетализации изображения устройств.
Структурная схема отображает принципработы устройства в самом общем виде. На схеме изображаются все основныефункциональные блоки, а также основные взаимосвязи между ними, указывающие напоследовательность взаимодействия функциональных блоков в схеме. Функциональныеблоки на схеме изображаются в виде прямоугольников или условных графическихобозначений. Наименования, типы или обозначения блоков вписываются внутрьпрямоугольников.
Функциональная схема служит для разъясненияи конкретизации видов процессов, происходящих в отдельных функциональныхблоках. Функциональная схема представляет собой гибрид структурной ипринципиальной. Некоторые наиболее простые блоки отображаются на ней, как наструктурной схеме, а остальные — как на принципиальной схеме. Функциональнаясхема дает возможность понять всю логику работы устройства, все его отличия отдругих подобных устройств, но не позволяет без дополнительной самостоятельнойработы воспроизвести это устройство.
Принципиальная схема являетсянаиболее полной электрической схемой устройства. Она обязательно показывает всеиспользованные в устройстве элементы и все связи между ними. Принципиальнаясхема должна позволять полностью воспроизвести устройство.
При построении корректирующих кодовиспользуют следующие параметры:
— основание кода (q) – число элементарных символов,выбранных для передачи сообщений;
— длина кода (n) – число символов, выбранных дляпередачи сообщений;
— количество информационных символов(k) – количество двоичных символов,несущих полезную информацию;
— кодовое расстояние (d) – количество позиций, которымиотличаются две сравнимые кодовые последовательности;
— кратность (количество) исправляемых(tисп) и обнаруживаемых (tоб) ошибок;
— скорость передачи кода (R) – характеризует количествоизбыточных символов приходящиеся на один информационный символ. Чем больше R, т.е. R→1 (Rвсегда меньше 1), тем эффективнее помехоустойчивый код, так как передаетсяменьше избыточной информации;
— число проверочных позиций в коде (r) – r = n — k;
— мощность (М) – число различныхкодовых комбинаций. Максимальное число кодовых комбинаций при заданных q и n равно Мmax=qn.
Код Хэмминга с параметрами (n; k) = (2m-1;2m-1-m) относится к разделимым кодам, следовательно, он задается спомощью проверочной матрицы. Проверочную матрицу Н можно задавать несколькимиспособами. Она должна содержать все ненулевые двоичные числа длиной m = r.
В курсовом проекте проверочнуюматрицу будем задавать с помощью элементов поля Галуа. Для формирования полявыбирается примитивный неприводимый порождающий полином степени r. Элементы поля находятся путемделения многочлена степени меньшей, чем n-1, на полином, являющийся неприводимым. Поскольку в качествестолбцов матрицы Н кода Хэмминга выбираются все ненулевые двоичные числа, томатрица Н – матрица степеней элемента поля α, где α– примитивный элемент поля, т.е H = [α0, α1, α2, α3,…αn-1].
Главной функцией кодера являетсяформирование проверочных уравнений, правило формирования которых определенопроверочной матрицей H.
Правило формирования проверочногосимвола для любой кодовой последовательности одинаково и определяется номерамипозиций логических единиц в каждой строке проверочной подматрицы проверочнойматрицы H. Используя систему формированияпроверочных символов, составляем структурную схему кодера.
2. РАСЧЕТ ПАРАМЕТРОВ КОДОВ ХЭММИНГА
Заданы исходные параметры кодаХэмминга:
— кодовое расстояние d0 = 3;
— число информационных символов k = 8 бит;
Используя эти параметры, рассчитаемосновные параметры кода Хэмминга. Код является двоичным, следовательно,основание кода q = 2, т.е.используются двоичные символы «1» и «0» .
Кратность (количество) исправляемыхошибок вычисляем по формуле
d0 = 2tи + 1, (1)
где d0– кодовое расстояние;
tи – количество исправляемых ошибок.
Кратность (количество) обнаруживаемыхошибок вычисляется по формуле
d0 = tоб + 1, (2)
где tоб – количество обнаруживаемых ошибок.
Таким образом, получаем, что данныйкод исправляет одиночную ошибку, т.е. tи = 1, иобнаруживает двойную, т.е. tоб= 2.
Для кодов Хэмминга, с d0= 3, т.е. корректирующих одиночные ошибки, количествоинформационных символов должно удовлетворять следующему равенству:
k = n – log2(n + 1). (3)
Используя это равенство, длина кода n = 12.
Число проверочных позиций r :
r = n – k, (4)
Следовательно, r = 4.
Итак, укороченный код Хэмминга имеетпараметры (n; k) = (12,8).
Для r = 4 полный код Хэмминга имеет параметры
(n; k) = (2r – 1; 2r – 1 – r) = (15,11).
Скорость передачи кода R вычисляется по формуле
R = k/n. (5)
Таким образом, R=8/12≈0.67.
3. РАЗРАБОТКА СТРУКТУРНОЙЭЛЕКТРИЧЕСКОЙ СХЕМЫ КОДЕРА
Код Хэмминга с параметрами (n; k) = (2m-1;2m-1-m) относится к разделимым кодам, следовательно, он задается спомощью проверочной матрицы. Проверочную матрицу Н можно задавать несколькимиспособами. Она должна содержать все ненулевые двоичные числа длиной m = r.
В курсовой работе проверочную матрицубудем задавать с помощью элементов поля Галуа. Для формирования поля выбираетсянеприводимый порождающий полином степени r:
q(x) = x4 + x3 + 1.
Элементы поля находятся путем делениямногочлена степени меньшей, чем n-1,на полином, являющийся неприводимым, т.е. на q(x).
Таким образом, получившиеся элементыполя приведены в таблице 1.
таблица 1 – Элементы поля Галуа
αi R(x)
HT
α0 1 1 0 0 0
α1 x 0 1 0 0
α2
x2 0 0 1 0
α3
x3 0 0 0 1
α4
1+ x3 1 0 0 1
α5
1+x+ x3 1 1 0 1
α6
1+x+x2+x3 1 1 1 1
α7
1+x+x2 1 1 1 0
α8
x+x2+x3 0 1 1 1
α9
x2+x3 0 0 1 1
α10
x+ x3 0 1 0 1
α11
1 +x2+x3 1 0 1 1
α12 1+x 1 1 0 0
α13
x+x2 0 1 1 0
α14
x2+x3 0 0 1 1
Поскольку в качестве столбцов матрицыH кода Хэмминга выбираются всененулевые двоичные числа, то матрица H – матрица степеней элемента поля α, т.е. H = [α0, α1, α2, α3,…αn-1].
Итак, получаем проверочную матрицуполного кода Хэмминга (15, 11):
/>
Чтобы в матрице информационные ипроверочные двоичные символы были разделены, приведем проверочную матрицу H(15,11) к приведено-ступенчатому виду:
/>
Чтобы получить матрицу Н кодаХэмминга с нужным числом информационных символов, в нашем случае k = 8, необходимо в проверочнойматрице полного кода исключить любые T = 3 столбцов, относящиеся к информационным разрядам, т.е. исключитьнужное число столбцов весом w≥2.Итак, исключим из матрицы H(15,11) три столбца смаксимальным весом.
Чем больше логических единиц вприписываемых строках проверочной матрицы, тем большей корректирующейспособностью обладает разрабатываемый код, но тем больше будет иметь кодексумматоров по модулю два и тем больше сложность его реализации. Следовательно,вычеркивание столбцов с максимальным весом приводит к уменьшению сложностивышеуказанных блоков. Проверочная матрица H укороченного кода (12, 8) имеет вид:
/>
Главной функцией кодера являетсяформирование проверочных уравнений, правило формирования которых определенопроверочной матрицей H(12,8). В матрице H(12, 8) символы a1, a2, a3…a8 – информационные, а a9, a10, a11, a12 – проверочные, которые могут бытьполучены путем суммирования по модулю два определенных информационных символов.
Правило формирования проверочногосимвола для любой кодовой последовательности одинаково и определяется номерамипозиций логических единиц в каждой строке проверочной подматрицы проверочнойматрицы H(12, 8). Так символ a1 формируется путем суммирования по модулю два информационныхсимволов. Итак, устройство кодирования (кодер) реализует нижеследующиеуравнения:
a9 = a1 + a2+ a3 + a6,
a10 = a2 + a3+ a5 + a6 + a7,
a11 = a3 + a4+ a7 + a8,
a12 = a1 + a2+ a4 + a5 + a8,
где под знаком "+"подразумевается суммирование по модулю два.
Используя полученную выше системуформирования проверочных символов, составим структурную схему кодера,представленную на рисунке 2:
/>
Рисунок 2 – Структурная электрическаясхема кодера кода Хэмминга
Рассмотрим принцип работы структурнойсхемы.
На вход кодирующего устройствапередаются в параллельном виде информационные символы a1, a2, a3…a8. Затем они поступают на блокформирования проверочных символов (БФПС), где из восьми информационных символовформируется 4 проверочных разряда в соответствии с уравнениями кодирования.Закодированная информация из кодирующего устройства передается в параллельномвиде.
4. РАЗРАБОТКА ФУНКЦИОНАЛЬНОЙЭЛЕКТРИЧЕСКОЙ СХЕМЫ КОДЕРА
Так как функциональная схема служитдля разъяснения и конкретизации видов процессов, происходящих в отдельныхфункциональных блоках, то в данном разделе основное внимание должно бытьобращено на выбор и обоснование принципа построения каждого функциональногоблока кодека, представленного на структурной электрической схеме кодека.
Функциональная схема представляетсобой гибрид структурной и принципиальной. Некоторые наиболее простые блокиотображаются на ней, как на структурной схеме, а остальные — как напринципиальной схеме. Функциональная схема дает возможность понять всю логикуработы устройства, все его отличия от других подобных устройств, но непозволяет без дополнительной самостоятельной работы воспроизвести этоустройство.
Функциональная схема кодерапредставлена на рисунке 4:
/>
Рисунок 4 – Функциональнаяэлектрическая схема кодера кода Хэмминга
Таким образом, кодер состоит изчетырёх сумматоров по модулю два, выходы которых соответствуют четырёмпроверочным символам. В функциональной схеме кодера используется параллельныйинтерфейс (совокупность средств и методов взаимодействия между элементамисистемы) ввода и вывода данных. Если один из проверочных символов равен единицы, то в данномканале присутствует ошибка, и, глядя на проверочные уравнения, можно сказать, вкаком именно разряде произошла ошибка, если же равно нулю, то ошибки нет вканале информации. В соответствии на выходе кодера формируется наше сообщение(а1… а8) и проверочные символы (а9… а12).
5. РАЗРАБОТКА ПРИНЦИПИАЛЬНОЙЭЛЕКТРИЧЕСКОЙ СХЕМЫ
КОДЕКА
5.1 ОБОСНОВАНИЕ ВЫБОРА ЭЛЕМЕНТНОЙБАЗЫ
С целью минимизации веса, габаритов иобъема оборудования кодера принципиальная схема кодера выполняется сиспользованием современных интегральных микросхем (ИМС).
Номенклатура выпускаемых интегральныхмикросхем обширна. Для построения устройств автоматики и вычислительной техникиширокое применение находят цифровые микросхемы, которые изготавливают постандартной технологии биполярных микросхем транзисторно-транзисторной логики(ТТЛ).
При выборе элементной базы, т.е.конкретной серии и типа ИМС, для разработки принципиальной схемы кодера кодаХэмминга необходимо, чтобы выполнялись следующие условия:
— потребление кодеком электроэнергиидолжно быть минимальным;
— ИМС должны иметь высокую степеньинтеграции, что обеспечит минимальный объем оборудования кодека;
— минимальная стоимость ИМС;
— ИМС должны обеспечивать надежнуюработу кодека и др.
В данной работе выбраны микросхемысерии К555. Отличие их от микросхем серии К155 – использование транзисторов сколлекторными переходами, зашунтированными диодами Шотки. В результатетранзисторы микросхем серии К555 не входят в насыщение, что существенноуменьшает задержку выключения транзисторов. К тому же они значительно меньшихразмеров, что уменьшает емкости их р-n-переходов.
5.2 РАЗРАБОТКА ПРИНЦИПИАЛЬНЫХ СХЕМФУНКЦИОНАЛЬНЫХ БЛОКОВ КОДЕРА
Распишем функциональные блоки дляпостроения принципиальной схемы преобразования параллельного двоичного кода вкод Хэмминга.
Код параллельно поступает наинформационные входы регистра, который представляет собой линейку из триггерови применяется для накопления (хранения) и сдвига данных. В данном случаеиспользуется восьмиразрядный регистр с разрешением записи К555ИР27. Егоусловное графическое обозначение представлено ниже
/>
1 – вход разрешения записи; 2 – выходинформационный первого разряда; 3 – вход информационный первого разряда; 4 –вход информационный второго разряда; 5 – выход информационный второго разряда; 6– выход информационный третьего разряда; 7 – вход информационный третьегоразряда; 8 – вход информационный четвёртого разряда; 9 – выход информационныйчетвёртого разряда; 12 – выход информационный пятого разряда; 13 – входинформационный пятого разряда; 14 – вход информационный шестого разряда; 15 –выход информационный шестого разряда; 17 – вход информационный седьмогоразряда; 18 – вход информационный восьмого разряда; 19 – выход информационныйвосьмого разряда.
Таблица истинности К555ИР27
/>
В итоге информационные исформированные проверочные символы поступают на ряд регистров (3), на выходеполучаем параллельный код. В этом случае используются четырёхразрядныеуниверсальные регистры К555ИР11А.
Условное графическое обозначениеК555ИР11А
/>
/>
/>
/>
Для построения принципиальной схемыблока формирования проверочных символов (БФПС) используются сумматоры серииК555ИМ5. Микросхема представляет собой два одноразрядных полных сумматора.
Условно-графическое изображение
/>
/>
/>/>
/>