18683

Принципы построения корректирующих кодов и их характеристики

Доклад

Информатика, кибернетика и программирование

Принципы построения корректирующих кодов и их характеристики. Коды делятся на: 1. Коды обнаруживающие ошибки. 2. Коды исправляющие ошибки. Все коды такого вида основаны на избыточности которую надо внести в кодовую комбинацию. Эта избыточность может быть введена ...

Русский

2013-07-08

24.75 KB

19 чел.

Принципы построения корректирующих кодов и их характеристики.

Коды делятся на:

1. Коды, обнаруживающие ошибки.

2. Коды, исправляющие ошибки.

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

По Хэммингу кодовое расстояние d(x,y) между двумя векторами x,y - число несовпадающих разрядов кода. Вес кода - число единиц в комбинации.

110

010

011

100

101

111

000

001

1. Пусть все комбинации разрешены.

Найдем min кодовое расстояние между комбинациями.

dmin=1

101

100 - при d=1 нет обнаружения ошибок.

2. Оставим только комбинации с dmin=2

Разрешенные комбинации:100,111,101,001.

100

110 - комбинации нет в разрешенных, ошибка.

Если dmin=2, можно обнаружить одиночную ошибку.

3) dmin=3

Разрешенные комбинации:100,011.

100

101 - принимаем за единицу ту комбинацию, до которой расстояние меньше, исправляем на 100.

Таким образом, чтобы код мог обнаруживать ошибки кратности r, надо чтобы min кодовое расстояние было r+1.

dminr+1

Чтобы код мог исправлять ошибки кратности l:

dmin ≥ 2l+1

Если надо исправлять ошибки кратности l и обнаруживать ошибки кратности r (r>l):

dminl+r+1

Характеристики корректирующих кодов.

1. Длина кода (количество информационных символов) – m.

2. Число контрольных символовk.

3. Длина кодовой комбинацииn.

n=m+k

4. Избыточность кода - h

Если используются не все комбинации, то:

,

N – общее число комбинаций, M – число разрешенных комбинаций.

5. Вероятность искаженной комбинации - Pи

Используется биномиальный закон распределения ошибки:

, q=1-p

Вероятность искажения всех комбинаций:

P0 - вероятность искажения одиночного двоичного символа в данном канале связи (устанавливается экспериментально). P0 ≈ 10-3…10-9

6. Вероятность правильной фиксации - Pпр

Pпр=1-Pи

7. Оптимальность кода.

Оптимальным является код, который исправляет max количество ошибок при min количестве контрольных символов.


 

А также другие работы, которые могут Вас заинтересовать

18359. Пример экзаменатора 59 KB
  6 урок Пример экзаменатора Рассмотрим простейший пример экзаменатора по географии задающий 5 вопросов по столицам государств. Рассмотрим варианты ввода как с заглавной так и со строчной буквы. Выполнение: Самостоятельно составьте экза
18360. Выбор 350 KB
  7 урок Выбор. Общий вид команды: выбор при условие 1 : серия 1 при условие 2 : серия 2 ... при условие n : серия n иначе серия n1 все Ключевое слово иначе вместе с соответствующей серией команд может отсутствовать: выбор при условие_1 : серия_1 при ус...
18361. Цикл N-раз 110.5 KB
  8 урок Цикл Nраз ознакомительно Общий вид цикла N раз: нц N раз серия команд кц Здесь N целое выражение задающее число повторений. При выполнении алгоритма последовательность команд циклически повторяется указанное число раз. Вывести на экран 10
18362. Цикл и генератор случайных чисел 111 KB
  10 урок. Цикл и генератор случайных чисел. rndвещ х Случайное число от 0 до x : при последовательных вызовах этой функции получается последовательность случайных чисел равномерно распределенных на [0х]. После выполнения заменяйте число 1 внутри rnd1 на 23 и т.д. ...
18363. Цикл внутри цикла 273 KB
  11 урок Цикл внутри цикла. Рассмотрим поэтапное решение а выведем на экран ряд чисел 6 штук через пробел. Обратите внимание на вывод нс после кц тем самым курсор переводится на следующую строку. опечатка в примере надо
18364. Рекуррентное соотношение 184 KB
  12 урок. Рекуррентное соотношение. Рекуррентным называется соотношение при котором очередной элемент последовательности выражается через предыдущий или предыдущие. Вычислить n элемент последовательности n задается с клавиатуры : 235917 где ...
18365. Цикл «Пока» 109 KB
  13 урок цикл Пока Общий вид цикла пока: нц пока условие тело_цикла кц При выполнении цикла пока КУМИР циклически повторяет следующие действия: Проверяет записанное после служебного слова пока условие. Если условие не соблюдается то выполнение цикла...
18366. Массивы - заполнение и простые действия 63 KB
  14 урок. Массивы 1 урокзаполнение и простые действия. Массивы описываются следующим образом: цел таб а[1:50] вещ таб а[1:50] Заполнение массива из 5 чисел внутри алгоритма и нахождение среднего арифметического этих...
18367. Массивы. Обработка элементов 222.5 KB
  15 урок. Массивы. Обработка элементов. Дан массив из 10 элементов вывести их на экран и рассчитать квадратный корень из nэлемента n11 вводится с клавиатуры. Дан массив целых чисел выяснить является ли nэлемент n11 вводится с