Лабораторная работа № 6 Коды с обнаружением ошибок

1. Код с проверкой на четность.

Такой код образуется путем добавления к передаваемой комбинации, состоящей из k информационных символов, одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемой комбинации было четным.

Пример 3.1. Построим коды для проверки на четность, где k - исходные комбинации, r - контрольные символы.

Определим, каковы обнаруживающие свойства этого кода. Вероятность P_oo обнаружения ошибок будет равна

Так как вероятность ошибок является весьма малой величиной, то можно ограничится

Вероятность появления всевозможных ошибок, как обнаруживаемых так и не обнаруживаемых, равна , где - вероятность отсутствия искажений в кодовой комбинации. Тогда .

При передаче большого количества кодовых комбинаций N_k, число кодовых комбинаций, в которых ошибки обнаруживаются, равно:

Общее количество комбинаций с обнаруживаемыми и не обнаруживаемыми ошибками равно

Тогда коэффициент обнаружения K_обн для кода с четной защитой будет равен

Например, для кода с k=5 и вероятностью ошибки коэффициент обнаружения составит . То есть 90% ошибок обнаруживаем, при этом избыточность будет составлять или 17%.

2. Корреляционный код (Код с удвоением). Элементы данного кода заменяются двумя символами, единица ‘1’ преобразуется в 10, а ноль ‘0’ в 01.

Вместо комбинации 1010011 передается 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10).

Например, при k=5, n=10 и вероятности ошибки , . Но при этом избыточность будет составлять 50%.

3. Инверсный код. К исходной комбинации добавляется такая же комбинация по длине. В линию посылается удвоенное число символов. Если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную комбинацию, если нечетное, то добавляемая комбинация является инверсной по отношению к исходной.

Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой основной группе символов. Если число единиц четное, то контрольные символы принимаются без изменения, если нечетное, то контрольные символы инвертируются. На втором этапе контрольные символы суммируются с информационными символами по модулю два. Нулевая сумма говорит об отсутствии ошибок. При ненулевой сумме, принятая комбинация бракуется. Покажем суммирование для принятых комбинаций без ошибок (1,3) и с ошибками (2,4).

Обнаруживающие способности данного кода достаточно велики. Данный код обнаруживает практически любые ошибки, кроме редких ошибок смещения, которые одновременно происходят как среди информационных символов, так и среди соответствующих контрольных. Например, при k=5, n=10 и . Коэффициент обнаружения будет составлять .

В соответствии с данными таблицы 3.1 составьте коды с обнаружением ошибок, рассмотренные выше.

Таблица 3.1 Варианты заданий

Примечание. Значения битов 2-ой информационной цепочки для вариантов 1-10 соответствуют столбцам 2-11 таблицы 3.1 начиная со строки «вариант 1» до строки «вариант 11». Значения битов 2-ой информационной цепочки для вариантов 11-20 соответствуют столбцам 2-11 таблицы 3.1 начиная со строки «вариант 11» до последней строки.