Кодирование методом Файра
683 ВведениеДеятельность людей связана с переработкой и использованием материалов, энергии и информации. Соответственно развивались научные технические дисциплины, отражающие вопросы технологии, энергетики и информатики. Информационная техника является сравнительно новой отраслью, получающей наибольшее развитие на этапе разработки и применения электронных вычислительных машин (ЭВМ) и автоматизированных систем управления (АСУ). Информационная наука теперь находит применение в самых разнообразных областях теории и практики. Центральной ветвью является теория связи, созданная Шенноном на основе теории вероятностей. С передачей и обработкой информации связаны действия любого автоматического устройства, поведение живого существа, творческая деятельность человека, развитие науки и техники, экономические и социальные преобразования в обществе и сама жизнь. Для более эффективного использования информации необходимо обмениваться информацией, что невозможно без её передачи по каналам связи. При передаче информации по каналам связи может происходить искажение передаваемой информации. Для предотвращения потерь полезной информации существуют различные методы защиты. Одним из них является кодирование информации при помощи помехозащищённых кодов. Двоичный код на все комбинации не является помехозащищённым, так как его комбинации отличаются друг от друга лишь в одном разряде, что не позволяет на приёмной стороне обнаружить и исправить возникшие ошибки. В этой связи возникает необходимость построения помехозащищённого кода. Помехозащищённые коды - это коды, которые позволяют обнаруживать и исправлять ошибки, то есть корректировать полученные сообщения. Для достижения помехозащищенности можно ввести избыточность добавлением дополнительных контрольных разрядов. Существует много различных алгоритмов построения помехозащищённых кодов. В данной работе рассматривается код Файра. Он является частным случаем группы циклических кодов. А именно, он относится к циклическим кодам, обнаруживающим и исправляющим пакеты ошибок. Циклические коды являются основным классом групповых помехоустойчивых кодов и используются для исправления и обнаружения ошибок, возникающих при передаче информации по каналу связи. Устройства, обнаруживающие и исправляющие ошибки, построенные на основе циклического кода, часто применяются в различных информационных системах. 1. Постановка задачи1.1 Анализ технического заданияВ соответствии с техническим заданием требуется построить математическую модель кода Файра, для количества передаваемых сообщений 128 и для корректирующей способности bs=2 (количество исправляемых ошибок) и br = 3 (количество обнаруживаемых ошибок). Найти образующую матрицу кода.Реализовать технические средства для его кодирования на уровне принципиальной схемы.В записке содержатся следующие приложения Документированный текст программы; Принципиальная схема кодера; Список элементов; Техническое задание. 1.2 Теоретическое введение1.2.1 Общие понятия и определенияПо условию задачи необходимо программно осуществить схему кодирования заданной кодовой. Также требуется привести техническую реализацию схему кодера в соответствии с заданием на курсовую работу.Коды Файра - это коды, обнаруживающие и исправляющие пакеты ошибок. Под пакетом ошибок длиной b понимают такой вид комбинации помехи, в которой между крайними разрядами, пораженными помехами, содержится b-2 разряда. Например, при b=5 комбинации помехи, т.е. пакет ошибок, могут иметь следующий вид: 10001 (поражены только два крайних символа), 11111 (поражены все символы), 10111, 11101, 11011 (не поражен лишь один символ), 10011, 11001, 10101 (поражены три символа). При любом варианте непременным условием пакета данной длины является поражение крайних символов.Коды Файра могут исправлять пакет ошибок длиной bs и обнаруживать пакет ошибок длиной br. В кодах Файра понятие кодового расстояния d не используется.Для кодов Файра, как и для всех циклических кодов вводятся понятия приводимых и неприводимых многочленов, а также образующих многочленов.Многочлен (полином), который можно представить в виде произведения многочленов низших степеней, называют приводимым (в данном поле), в противном случае - неприводимым. Неприводимые многочлены играют роль, сходную с простыми числами в теории чисел. Неприводимые многочлены P(X) можно записать в виде десятичных или двоичных чисел (10011), либо в виде алгебраического многочлена. Многочлен в поле двоичных чисел называется неприводимым, если он делится без остатка только на себя и на единицу. В основу циклических кодов положено использование неприводимого многочлена P(X), который применительно к циклическим кодам называется образующим.Образующий многочлен кода Файра Р(Х)ф определяется из выражения:Р(Х)ф = Р(Х) (Хc+1) (1.1)где Р(Х) - неприводимый многочлен степени l.Из принципа построения кода следует, чтоl ? bs, (1.2)c ? bs +br-1. (1.3)При этом с не должно делиться нацело на число е: е=2l-1. (1.4)Неприводимый многочлен Р(Х) выбирают из таблицы 1.1 согласно уравнению (1.2), но так, чтобы удовлетворялось условие (1.4). Длина слова n равна наименьшему общему кратному чисел с и е, так как только в этом случае многочлен Хn+1 делится на Р(Х)ф без остатка:n=НОК (е, с). (1.6)Число контрольных символов:m=c+l. (1.5)Таблица 1.1. Неприводимые многочлены и их эквиваленты|
Р(Х1)=Х+1>3>11 | Р(Х5)= Х5+Х3+Х2+Х+1>47>101111 | | Р(Х2)=Х2+Х+1>7>111 | Р(Х5)= Х5+Х4+Х2+Х+1>55>110111 | | Р(Х3)=Х3+Х+1>11>1011 | Р(Х5)= Х5+Х4+Х3+Х+1>59>111011 | | Р(Х3)= Х3+Х2+ 1>13>1101 | Р(Х5)= Х5+Х4+Х3+Х2+1>61>111101 | | Р(Х4)=Х4+Х+1>19>10011 | Р(Х6)= Х6+Х+1>67>1000011 | | Р(Х4)=Х4+Х3+1>25>11001 | Р(Х7)= Х7+Х3+1>137>10001001 | | Р(Х4)= Х4+Х3+ Х2+Х+1>31>11111 | Р(Х8)= Х8+Х4+Х3+ Х2+1>285>100011101 | | Р(Х5)= Х5+Х2+1>37>100101 | Р(Х9)= Х9+Х4+1>1041>1000010001 | | Р(Х5)= Х5+Х3+1>41>101001 | Р(Х10)= Х10+Х3+ 1>2057>10000001001 | | |
Коды Файра являются помехоустойчивыми кодами и используются для исправления и обнаружения ошибок, возникающих при передаче информации по каналу связи. Способность кода обнаруживать и исправлять ошибки обусловлена наличием в кодовом слове помимо информационных разрядов избыточных (проверочных) символов, значения которых вычисляются при кодировании по определенным алгоритмам. Проверка значений этих символов на приемной стороне, также выполняемая по определенным алгоритмам, позволяет обнаруживать и исправлять ошибки.В кодах Файра каждая комбинация кодируется самостоятельно (в виде блока) таким образом, что информационные k и контрольные m символы всегда находятся на определенных местах:10101010 10010k mn=m+k.Причем следует помнить, что в данном случае мы используем в качестве символов - биты информации. Т.е. один символ - может быть представлен двумя способами: либо «1», либо «0».В общем случае, если заданную кодовую комбинацию Q(X) умножить на образующий многочлен P(X), получится, обладающий теми или иными корректирующими свойствами в зависимости от выбора P(X). Однако в этом коде контрольные символы m будут располагается в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно упростить, если контрольные символы приписать в конец кода.Групповые коды с такой структурой принято обозначать (n, k) кодами, отражая таким образом в названии кода общую длину кодового слова и количество информационных символов, на передачу которых рассчитан код.При описании циклических кодов n разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной Х. Показатели у переменной Х соответствуют номерам разрядов (начиная с нулевого), а коэффициентами при Х для двоичных кодов будут 0 и 1. Например, кодовая комбинация 1011 в виде многочлена запишется следующим образом:Члены с нулевыми коэффициентами при записи многочлена опускаются, и окончательно получим: Наибольшая степень Х в слагаемом с ненулевым коэффициентом называется степенью многочлена. Все действия над кодовыми комбинациями сводятся действиям над многочленами [2, 3].Способность кодов Файра обнаруживать и исправлять ошибки связана с тем, что разрешенные кодовые комбинации будут делиться на g(x) без остатка, а запрещенные кодовые комбинации будут давать остатки, по виду которых можно обнаружить и исправить ошибку.Итак, исходя из вышеописанного, можно дать такую математическую модель решаемой задачи.1.2.2 Общая математическая модель и оптимальные методы решения поставленной задачи По условию задачи для декодирования переданных кодовых последовательностей необходимо воспользоваться кодами Файра. Это такие коды, которые могут обнаруживать и исправлять пакеты ошибок. Для того, чтобы представить код заданного числа разрядов в виде кодов Файра, необходимо провести ряд вычислений. Требуется найти остаток, удовлетворяющий ряду требований. Эти требования можно выразить в виде неравенств и уравнений (1.1) - (1.5). Это и будет математическая модель для задания на курсовую работу. Этот код является одним из наиболее эффективных циклических кодов. Возможность обнаружения и исправления практически любых ошибок при относительно малой избыточности по сравнению с другими кодами, а также простота технической реализации аппаратуры кодирования и декодирования делает эти коды широко распространенными. В кодировании избыточность определяется отношением контрольных символов m к длине слова: И = m/n, где n=m+k [2]. Так, для кода Файра (120, 108) с исправляющей способностью bs=4 избыточность будет составлять: И=12/120=0,1. С другой стороны, для одной из разновидности циклических кодов - кодов БЧХ (127, 99) (взято близкое значение n к рассмотренному ранее коду Файра) с такой же исправляющей способностью исправляющая способность будет равна: И=28/127=0,22, т.е. значительно выше, чем у кода Файра. Это очевидно: исправить четыре ошибки, находящиеся в одном месте, проще, чем ошибки, рассредоточенные по всей длине комбинации [2]. 1.2.3 Пример построения кодов ФайраРассмотрим на примере.Пусть требуется построить код Файра для bs=4, br=5.Исправить пакет bs=4 - значит исправить одну из следующих комбинаций ошибок, пораженных помехами: 1111, 1101, 1011 и 1001. В тоже время этот код может обнаружить одну из комбинаций в пять символов, рассмотренных ранее: 10001, 11111 и т.д.На основании (1.2) и (1.3) c?8 и l?4. По таблице 1.1 находим неприводимый многочлен четвертой степени: Р(Х)=Х4+Х+1.Согласно (1.4), е=24-1=15. Поэтому длина кода n=15*8=120. Из (1.5) число контрольных символов m=8+4=12, то есть в данном случае оно равно степени образующего многочлена. В итоге получаем код (120, 108). Избыточность такого кода, если учитывать его исправляющую способность, невелика: И=12/120=0,1.Проверочные символы получаются при делении исходного кода с приписанными m нулями на образующий многочлен кода Файра. Это можно выразить в виде формулы: Таким образом, остаток от деления R(x) и будет образовывать проверочные символы. Приписывание m нулей соответствует умножению на хm. Итак, мы получаем код:F(x) = G(x) · xm + R(x)1.2.4 Матричная запись кодаПолная образующая матрица циклического кода составляется из двух матриц: единичной (соответствующей k информационным разрядам) и дополнительной матрицы (соответствующей проверочным разрядам) [2]. По образующей матрице можно рассчитывать все кодовые комбинации.Нахождение элементов дополнительной матрицы.Дополнительную матрицу находят путем деления единицы с нулями на выбранный многочлен Р(Х) и выписывания всех промежуточных остатков. При этом должны быть соблюдены следующие условия:а) число остатков должно быть равно числу информационных символов k;б) для дополнительной матрицы пригодны лишь остатки с весом W, не меньшим числа обнаруженных ошибок r, т.е. в данном случае не меньшим 3 (W?3); так как обнаруживается не менее трех ошибок.Из условий а) и б) определяется количество нулей, приписываемых к единице при делении ее на многочлен Р(Х);в) так как элементы дополнительной матрицы являются для данной комбинации контрольными символами, то число разрядов дополнительной матрицы равно числу контрольных символов m. Вследствие того, что степень образующего многочлена выбирают равной m, число разрядов дополнительной матрицы равно также степени образующего многочлена. Разрядность остатка равна степени образующего многочлена.
Страницы: 1, 2, 3, 4
|
