Cибирский Государственный Университет
телекоммуникаций и информатики
Кафедра СРС
«Блочные коды с коррекцией ошибок»
Выполнили: студентки
группы М-12
Шачнева Е.А.
Баркеева К.С.
Проверила: Носкова Н.
Новосибирск 2005
Блочные коды с коррекцией ошибок
Методы обнаружения ошибок широко применяются на практике в протоколах управления каналами передачи данных, таких, как HDLC, а также в транспортных протоколах, таких, как TCP. В то же время под использованием кодов обнаружения ошибок подразумевается повторная передача блоков данных согласно процедуре ARQ). Для беспроводных приложений такой подход неприемлем по двум причинам.
1.Уровень ошибок в беспроводном канале может быть довольно высок; в результате потребуется значительное число повторных передач.
2.В некоторых случаях, особенно в спутниковой связи, задержка распространения сигнала довольно велика по сравнению с временем передачи одного кадра. При большом расстоянии между приемником и передатчиком ошибка в одном кадре приводит к необходимости повторной передачи множества кадров.
Вместо повторной передачи было бы лучше, если бы приемник мог исправлять ошибки в полученном сигнале, используя информацию, содержащуюся в самом сигнале. На рис.1 представлена схема реализации этой идеи. С помощью кодера FEC (forward error correction— прямое исправление ошибок) передатчик преобразует каждый k-битовый блок данных в n- битовый блок (n>k), именуемый кодовым словом, который затем передается (в беспроводной связи для передачи используется созданный модулятором аналоговый сигнал). При распространении сигнал может подвергаться воздействию шума, что может привести к появлению ошибочных битов. Приемник демодулирует полученный сигнал, преобразовывая его в строку битов, подобную переданной, но, возможно, с ошибками. Полученный блок данных обрабатывается декодером FEC, в результате возможны такие ситуации.
1.При отсутствии ошибочных битов вход декодера FEC идентичен исходному кодовому слову, так что на выход декодера поступает исходный блок данных.
2.Декодер может обнаружить и исправить определенные последовательности ошибок. Поэтому даже если вход декодера отличается от исходного кодового слова, из него можно получить исходные данные.
3.Некоторые последовательности ошибок могут быть обнаружены декодером, но не могут быть исправлены. В этом случае декодер сообщает о наличии неисправимой ошибки.
4.Наличие некоторых (обычно довольно редких ) последовательностей ошибок не может быть обнаружено декодером. В результате декодер преобразовывает входной n-битовый блок в k- битовую последовательность, которая отличается от переданной, но которую кодер считает правильной.
Рис.1 Прямое исправление ошибок
Декодер исправляет ошибки с помощью добавления избыточных данных к передаваемому сообщению. Избыточность позволяет приемнику восстановить исходное сообщение даже при наличии определенного уровня ошибок.
В алгоритме FEC к входному k- битовому блоку данных добавляется (n-k) контрольных битов; в результате размер передаваемого блока составляет n бит; все биты исходного k- битового блока содержатся в полученном n-битовом блоке. Для некоторых схем прямого исправления ошибок входная k-битовая последовательность так преобразовывается в n- битовое кодовое слово, что исходные kбит не фигурируют явно в кодовом слове.
Принципы блочных кодов
Расстоянием Хэмминга d(v1 ,v2) между двумя n-битовыми двоичными последовательностями v1 и v2 называют число несовпадающих разрядов v 1 и v2. Например, если v1=011011
v2 = 110001,
то d(v1, v2)=3
Рассмотрим теперь метод блочного кодирования с целью коррекции ошибок. Пусть требуется передать определенное количество k-битовых данных. Вместо передачи каждого блока как последовательности k-бит, преобразуем каждую k-битовую последовательность в уникальное n-битовое кодовое слово.
Пример. Для k=2 и n=5 имеем следующее присвоение:
Блок данных Кодовое слово
00 00000
01 00111
10 11001
11 11110
Предположим, что кодовое слово было получено в виде последовательности битов 00100. Поскольку эта последовательность не соответствует ни одному из кодовых слов, приемник обнаружил ошибку. Kaк можно её исправить? Точно узнать, какой из блоков данных был передан, невозможно, поскольку шум мог изменить 1,2,3,4 или даже все 5 переданных блоков. Отметим, впрочем, что для преобразования приемлемого кодового слова 00000 в полученную последовательность достаточно изменения одного бита. Соответственно, для преобразования 00111 в 00100 нужно изменить два бита; 11110 в 00100 — три бита; 11001 в 00100— четыре бита. Таким образом, можно сделать вывод, что с наибольшей вероятностью был передан блок 00000,т.е. искомый блок данных -00. Подобное рассуждение и есть логика коррекции ошибки. Используя понятие "расстояние Xэмминга", его можно представить в следующей виде:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
