Спирина, М.С. Дискретная математика

В процессе декодирования принимается решение относительно истинного значения закодированного слова с учетом статисти­ ческого характера самой гипотезы. Поэтому при конструировании кода очень важен выбор модели канала с помехами. Наиболее рас­ пространенными считаются симметричные каналы с равноверо­ ятными ошибками различных типов, для которых наиболее пол­ но разработана математическая модель. Систематический код. Рассмотрим математическую сторону раз­ деляемого систематического кода. Кроме информационных он содержит контрольные разряды, в которые записывается информация о слове, т.е. та самая избыточ­ ность, необходимая для диагностики ошибок. Пусть к — количество контрольных разрядов, т — количество информационных разрядов, п — число разрядов в информацион­ ном слове. Представим это на отрезке в виде схемы (рис. 6.8). Корректирующая способность кода численно равна вероятно­ сти обнаружения и исправления ошибок. Пусть вероятность искажения одного разряда кодового слова рав­ на р. Если искажены все к символов, причем каждый с вероятностью р, то по правилу произведения вероятностью их искажения будет р к. Тогда остальные п - к символов сохранены с вероятностью 1 - р, что по правилу произведения даст (1 - р)п~к. Так как в кодовом слове учитывается и вероятность искажения, и вероятность сохра­ нения символов, то по правилу произведения их вероятность равна р к( 1 - р)п~к. Для определения количества комбинаций применим формулу сочетаний, так как число кодовых комбинаций из всего множества символов п по к искажениям не зависит от порядка. Для вычисления вероятности искажения информации надо учесть чис­ ло комбинаций сохраненных и искаженных символов в кодовом слове, а также вероятность их сохранения в п - к разрядах и вероят­ ность их искажения в к разрядах. Тогда по правилу произведения корректирующая способность кода равна Р = I /=1 я! / ! ( « - / ) ! р ‘(1 -р )п-‘ . Было установлено, что наибольший вес в сумме вероятностей имеет вероятность искажения одного символа р е [ 1СИ; 10_3]. Это подтверждает тот факт, что легче обнаружить и исправить одну ошибку. Введем ряд определений. Назовем весом кодовой комбинации К(Д) количество единиц в кодовой комбинации. Например, пусть А = 01001101, В = = 11011001. Вес кодовых комбинаций составляет К(Д) = 4, У(В) = 5. Назовем кодовым, или хемминговым, расстоянием d(A, В) для кодовых ком- Рис. 6.8. Схема для пред­ ставления систематиче­ ского кода 321