11.2.3.Однонаправленные системы с исправлением стираний

Наряду с обнаружением и исправлением ошибок в однонаправленных системах в целях защиты от ошибок можно применять декодирование с исправлением (восстановлением) стираний элементов кодовых комбинаций. Способность помехоустойчивого кода восстанавливать стирания определяется следующими утверждениями:

1.Кратность гарантийно восстанавливаемых стираний помехоустойчивым (n,k)-кодом должна быть меньше минимального кодового расстояния z ≤ d_мин – 1 этого кода, т.к. только при этом условии возможно установление однозначного соответствия между комбинациями со стёртыми элементами и одной из разрешённых комбинаций. Если положить число стираний z = d_мин , то стёртая комбинация с одинаковой вероятностью может быть отождествлена с 2 различными разрешёнными комбинациями т.е. кратность гарантийно восстанавливаемых стираний совпадает с кратностью гарантийно обнаруживаемых ошибок.

2.Кратность гарантийно восстанавливаемых стираний не может быть больше числа избыточных элементов (n,k)-кода, т.к. для однозначного восстановления кодовой комбинации, пораженной стираниями, необходимо, чтобы не менее k любых элементов кодовой комбинации были не искажены, т.е.: z ≤ n - k .

Итак, число восстанавливаемых стираний (n,k)-кодом N_z лежит в пределах: ≤ N_z ≤ . Для оценки вероятности ложного восстановления стертых элементов используют модель двоичного стирающего канала. Эта модель характеризуется тремя параметрами:

- q₁ – вероятность правильного приема единичного элемента,

- p₁ - вероятность приема единичного элемента стертым,

- p₂ - вероятность ошибочного приема единичного элемента.

Справедливо : q₁ + p₁ + p₂ = 1.

Вероятность ложного восстановления:

Р_ошz .

Расчеты и экспериментальные исследования показали, что эта вероятность меньше чем вероятность необнаружения ошибок для канала без стираний элементов т.е. применение стираний элементов эквивалентно введению дополнительной избыточности в передаваемое сообщение. Обозначим результирующую избыточность в кодовой комбинации (n,k)-кода, при которой достигается вероятность необнаружения ошибок в двоичном симметричном канале с параметром р численно равная вероятности ложного восстановления стираний в двоичном стирающем канале при использовании помехоустойчивого кода той же длины n, через т. Тогда

,

откуда получим:

Здесь ∆т- выигрыш по избыточности при введении стираний. Экспериментальные данные показывают, что для каналов среднего качества ∆т = 1-3.

Относительная скорость в системах с исправлением стираний при использовании (n,k)-кода равна: R_о = k/n.

Исправление стираний на ранних стадиях эксплуатации систем передачи данных осуществляли методом подбора подходящих значений – методом проб и ошибок. На современном этапе стирания исправляют методом быстрого декодирования .

11.3. Задачи

1. Определить необходимое число повторов кодовой комбинации в однонаправленной системе передачи данных при удаленном вводе данных от терминала, работающего на коде КОИ-7, в ЭВМ, если ошибки в канале ввода распределены по независимому закону с вероятностью р = 10^-3, а ЭВМ требует, чтобы вероятность искажения вводимых знаков не превышала 10^-6. Задачу решить для случаев позначной и поэлементной обработки.

2. В однонаправленной системе передачи метеоданных, допускающей появление стертых комбинаций на выходе канала передачи данных, используется циклический (n,k)-код с n = 255 и с порождающим многочленом g(х) = х¹⁶+х¹²+х⁵+1 в режиме обнаружения ошибок. Требуется оценить вероятность неискаженных и стертых комбинаций на выходе канала передачи данных. В дискретном канале имеет место группирование ошибок. Параметры дискретного канала: р = 10^-3, α = 0,5.

3. Систему передачи данных из предыдущей задачи решили использовать для передачи итогов голосования. При этом ввели многократное повторение комбинаций (n,k)-кода и потребовали, чтобы вероятность появления стертых комбинаций не превышала вероятности необнаружения ошибок. Каково должно быть число повторов каждой комбинации при использовании обработки принятых комбинаций по методу последовательного замещения комбинаций с обнаруженными ошибками?

4. Оценить выигрыш от декорреляции ошибок в однонаправленной системе передачи данных с исправлением ошибок при использовании кода Голея (23,12) с d_мин= 7, если параметры исходного дискретного канала: р = 10^-3, α = 0,5.