Разработка программного имитатора цифрового канала связи с применением помехоустойчивого кодирования
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? выбран так, что результат чётный, то говорят, что схема имеет положительную чётность; если при добавлении бита чётности результирующий блок данных является нечётным, то говорят, что он имеет отрицательную чётность. В нашей задаче используется код с положительной чётностью. Этот код не может исправить ошибку. С его помощью можно только обнаружить, что в кодовом символе присутствует нечетное количество ошибок. Если ошибка была внесена в четное количество бит, то проверка четности покажет отсутствие ошибок.
Линейные блочные коды - это класс кодов с контролем четности, которые можно описать парой чисел . В процессе кодирования блок из символов сообщения (вектор сообщения) преобразуется в больший блок из символов кодового слова (кодовый вектор), образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов (0 и 1), код является двоичным и включает двоичные разряды (биты).
-битовые сообщения формируют набор из последовательностей сообщения, называемых -кортежами (последовательностями цифр), -битовые блоки могут формировать последовательности, также именуемые -кортежами. Процедура кодирования сопоставляет с каждым из -кортежей сообщения один из -кортежей. Блочные коды представляют взаимно однозначное соответствие. Для линейных кодов преобразование отображения является, конечно же, линейным. Операции над двоичными компонентами производятся по правилам арифметики по модулю 2.
Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга кодового слова определяется как число ненулевых элементов в . Для двоичного вектора это эквивалентно числу единиц в векторе. Расстояние Хэмминга между двумя кодовыми словами и , обозначаемое как , определяется как количество элементов, в которых они отличаются. Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух двоичных векторов является другим двоичным вектором, двоичные единицы которого расположены на тех позициях, которыми эти векторы отличаются. Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами равно весовому коэффициенту Хэмминга их суммы, то есть,
.
Также видно, что весовой коэффициент Хэмминга кодового слова равен его расстоянию Хэмминга до нулевого вектора.
В блочном коде, прежде чем исправлять ошибки, необходимо их обнаружить. (Или же код может использоваться только для определения наличия ошибок.) Возможность определения наличия ошибки дается следующим выражением . Блочный код с минимальным расстоянием гарантирует обнаружение всех моделей ошибок, содержащих или меньшее число ошибочных бит. Способность кода к исправлению ошибок определяется, как максимальное число гарантированно исправимых ошибок на кодовое слово, и записывается следующим образом
.
Возможность исправления ошибок следует из гарантированного максимума . Код можно использовать для одновременного исправления и обнаружения ошибок, причем , а минимальное расстояние кода дается следующим выражением
.
Наиболее известным линейным систематическим кодом является блоковый код Хэмминга. Коды Хэмминга - это простой класс блочных кодов. Систематический линейный блочный код - это такое отображение -мерного вектора сообщения в -мерное кодовое слово, в котором часть генерируемой последовательности совмещается с символами сообщения. Остальные бит - это биты четности.
Количество контрольных разрядов должно быть выбрано так, чтобы удовлетворялось неравенство . При строгом равенстве код называется оптимальным, иначе - неоптимальным.
Если в кодовой комбинации ошибки нет, то проверочное число содержит только нули. Если в низшем разряде числа стоит 1, это означает, что в результате первой проверки обнаружена ошибка. При первой проверке проверяются те номера позиции, двоичные представления которых имеют в младшем разряде единицы. Таким образом, первая проверка охватывает позиции 1, 3, 5, 7, 9, 11, 13 и т.д. Для второй проверки выбираются такие позиции, двоичные представления которых имеют единицу во втором разряде. Следовательно, вторая проверка будет охватывать позиции 2, 3, 6, 7, 10, 11, 14 и т.д. И так далее. Остается решить, какие позиции в коде целесообразно использовать для передачи информации, а какие - для проверки. Выбор для проверки позиций 1, 2, 4, 8 и т.д. имеет преимущество, состоящее в том, что каждая из этих позиций встречается только в одной проверяемой группе символов. Каждый контрольный бит является битом чётности для своей проверочной группы.
В имитаторе реализован код Хэмминга для исправления однократных ошибок. Для кодирования номера исходный байт с АЦП расширяется на количество проверочных бит. Номера позиций с единичными битами суммируются по модулю два и биты из полученного числа расставляются в позиции контрольных бит в кодируемом байте.
Важным подклассом линейных блочных кодов являются двоичные циклические коды[4]. Линейный код называется циклическим, если он обладает следующим свойством. Если -кортеж является кодовым словом в подпространстве S, тогда , полученный из с помощью циклического сдвига, также является кодовым словом в S. Или, вообще, , полученный циклическими сдвигами, является кодовым словом в S.
Компоненты кодового слова можно рассматривать как коэффициенты полинома :
Полиномиальную функцию можно рассматривать как "заполнитель" разрядов кодового слова , т.?/p>