Министерство образования Республики Беларусь
Белорусский государственный университет
информатики и радиоэлектроники
Кафедра метрологии и стандартизации
" __" 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].