УДК 681.51:57
В.А. ЛИТВИНОВ, С.Я. МАЙСТРЕНКО, Ю.Г. ПИЛИПЕНКО
ИСПРАВЛЕНИЕ ОШИБОК ПОЛЬЗОВАТЕЛЯ НА ОСНОВЕ СОВМЕСТНОГО ПРИМЕНЕНИЯ ПОМЕХОЗАЩИТНЫХ КОДОВ И ВИРТУАЛЬНОГО СЛОВАРЯ ДОПУСТИМЫХ СЛОВ
Abstract: The descibed model of the automatic error correction is based on the joint application of the code methods and method of the inverse distortion for increasing validity of the input information and saving labor of error correction. The combined algorithms of automatic and semiautomatic error correction are considered. For the proposed algorithms, probabilistic estimations of the automatic, semiautomatic, manual and false correction, which can be used while deciding which algorithm of adjustment to choose, are analytically derived.
Анотація: Описана модель автоматичного виправлення помилок ґрунтується на сумісному використанні кодових методів та методу зворотних спотворень для підвищення достовірності вхідної інформації й зниження трудомісткості виправлення помилок. Розглядаються комбіновані алгоритми автоматичної та напівавтоматичної корекції помилок. Для запропонованих алгоритмів аналітично отримані ймовірнісні оцінки автоматичної, напівавтоматичної, ручної та хибної корекції, які можуть використовуватись при прийнятті рішень відносно вибору алгоритму корекції.
Ключові слова: помилки користувача, автоматична корекція, достовірність даних, перешкодозахисні коди.
Аннотация: Описанная модель автоматического исправления ошибок основана на совместном применении кодовых методов и метода обратных искажений для повышения достоверности входной информации и снижения трудоемкости исправления ошибок. Рассматриваются комбинированные алгоритмы автоматической и полуавтоматической коррекции ошибок. Для предлагаемых алгоритмов аналитически получены вероятностные оценки автоматической, полуавтоматической, ручной и ложной коррекции, которые могут быть использованы при принятии решений относительно выбора алгоритма корректировки.
помехозащитные коды.
Известны и описаны в литературе методы помехозащитного кодирования, предназначенные для повышения достоверности входной алфавитно-цифровой информации путем автоматического исправления ошибок пользователя. Наиболее полный обзор таких методов приведен в [1]. Большинство этих методов ориентировано на автоматическое исправление однократных ошибок типа замены значения одного символа и обнаружение с последующим «ручным» исправлением ошибок иных классов.
Помехозащитные коды с исправлением ошибок (КИО) применяются для защиты информации в каналах связи, где вероятность появления ошибок, кратности более 1, значительно, на несколько порядков меньше вероятности однократной ошибки. Поэтому относительное количество не автоматически исправленных ошибок сравнительно невелико. Для информации, вводимой пользователем, положение иное. Здесь, как известно, ошибки типа, например, пропуска символа имеют кратность от 1 до n в зависимости от позиции пропущенного символа, а вероятность такой ошибки не намного меньше вероятности однократной транскрипции. По этим причинам относительное количество вручную исправляемых ошибок здесь может быть значительным.
Метод, позволяющий в этих случаях уменьшить долю ошибок, исправляемых вручную, и снизить тем самым общую трудоемкость ввода и корректировки информации, заключается в расширении штатной процедуры декодирования КИО за счет привлечения метода обратных искажений («вариаций» ошибочного слова) и проверки корректности значения вариации по
словарю допустимых слов [2]. При отсутствии реального словаря в качестве такового может быть использован виртуальный словарь (см. далее).
В статье решается задача построения модели и оценки существенных характеристик
метода.
Введем следующие обозначения и допущения:
q,пи,пк - соответственно алфавит, количество информационных символов, количество
контрольных символов входного слова, пи + пк = п ;
Е = {К,} - множество классов возможных ошибок;
р. - относительное количество ошибок класса Е. в потоке вводимых слов;
Ек - подмножество классов ошибок, на автоматическое исправление которых ориентирован конкретный КИО, и назовем их первично корректируемыми ошибками;
Е2 - подмножество классов ошибок, идентифицируемых виртуальным словарем (вторично корректируемые ошибки);
Т - виртуальный словарь - множество слов, удовлетворяющих условию отсутствия ошибки, определенному контрольным соотношением (алгоритмом кодирования-декодирования)
используемого КИО. Мощность Т не превышает qn;
г =---- - коэффициент избыточности кода, определяющий относительное количество
всевозможных комбинаций значений п символов, не удовлетворяющих условию вхождения в Т .
Примем допущение, что значения вариаций ошибочного слова случайно распределены среди qn всевозможных значений слов. В этом случае процесс генерации вариаций и их сравнения с Т мы можем описать моделью испытаний Бернулли, для которой вероятность Р^,г,У) случайного совпадения в точности g вариаций из V проверяемых, при условии, что вероятность одного случайного совпадения равна г определяется известной формулой биноминального распределения:
Р(^г,Г) = С^¥г-g .
Общая схема комбинированной процедуры включает два этапа.
обнаруживается и автоматически исправляется. Иначе, слово идентифицируется как неисправимо ошибочное (в смысле возможностей кода). Переход к этапу 2.
каждой вариации слова на принадлежность Т (т.е., по сути, многократное повторение этапа 1 для генерируемых вариаций). В зависимости от результатов проверки возможно автоматическое или полуавтоматическое исправление в соответствии с алгоритмами, описанными в [2].
При этом возможны следующие финальные исходы.
ЯАК, КПАК - ошибка правильно идентифицирована и исправлена автоматически (вероятность РАК) или полуавтоматически, т.е. с подтверждением пользователя (вероятность
ЯРК - идентифицировать ошибку не удается и она исправляется полностью „вручную” (вероятность РРК);
ЯЛК - ошибка идентифицирована неверно и исправлена ложно (вероятность РЛК).
Определение этих вероятностей и является целью построения следующих моделей. Под вероятностями здесь и далее понимается относительное количество исходов, “благоприятных” в определенном конкретном смысле.
вторичной корректировки (алгоритм А) определяет вероятностно-логический граф, приведенный на рис. 1. За основу принят алгоритм однозначной корректировки вторично корректируемой ошибки
[2]. В этом случае автоматическое исправление ошибок Е2 производится только при единственном
совпадении вариации со словарем (т.е. при отсутствии синонимов).
Последовательность х дуг графа означает совместное наступление х независимых событий; финальная вероятность последнего события равна произведению вероятностей, приписанных каждой дуге; разветвление у дуг означает наступление одного из у несовместных событий; суммарная вероятность событий по у разветвляющимся дугам, равная сумме соответствующих вероятностей, должна быть равна 1, как полная группа событий. Сумма финальных вероятностей по листьям дерева должна быть равна 1, а для искомых вероятностей Р должны выполняться условия:
Таким образом, приведенный граф отражает структуру финальных вероятностей независимых событий.
На рис. 1 приняты следующие обозначения событий и их вероятностей:
Б21 - ошибка обнаружена с вероятностью Ж21 = 1 — г ;
$22 = $21 - ошибка не обнаружена с вероятностью Р22 = г ;
Б211 - ошибка принята для идентификации и исправления с вероятностью Р211 = 1 — ¡; Б212 = Б2П - ошибка ложно исправлена кодом с вероятностью Р212 = р ;
Б2111 - ошибка е Е2 с вероятностью П2Ш = Р2;
S2 -і Р
Р21111 S21111
Рис. 1. Граф частных событий для алгоритма автоматического исправления S2112 = S2111 - ошибка £ E^ с вероятностью Р2112 = 1 -P2;
p21112 = I P(g,r,V — V = 1—P( 0,r,V — 1); g =1
для ошибки, которая не принадлежит Е?, не состоялось ни одного случайного
совпадения вариации со словом
словаря
с вероятностью
Р21121 = 1 - P(1,r,V) = 1 - rV(1 - r)V ;
$21122 = $21121 - ошибка, которая не принадлежит Е2, однозначна (г = 1) с вероятностью
Р21122 = Р( 1,гУ) = ^ (1 - Г ) .
С учетом приведенных обозначений и вида графа рис. 1 можно записать такие логические выражения:
РЛК = Я1 у (Я2 Л Я21 Л Я211 Л Я2111 Л Я 21111 )’’
*РК = Л *21 Л Я,! )Л((*2111 Л *21112 М*2112 Л ^1121 ))‘
^ ЛК = ($2 Л $21 Л $211 )л ((Я2112 Л *21122 ) V Я 212 ) .
С учетом того, что все события на рис. 1 взаимно независимы, для вероятностей
РАК’ РРК ’ РЛК можно записать
Р — П + П * П * П * П * П ;
АК 1 2 21 211 2111 21111 ’
P — П * П * П * (п * П + П * П );
РК 2 21 211 V 2111 21112 2112 21121 /’
■ П * * (п * П * + П ).
Окончательно имеем
РАК — P+(1 - P)(1 - ^ )(1 - в) Р (1 - г)’"-1;
РРК& —(1 - P)(1 - r )(1 - в) к \\ 1 -(1 - r Г 1 + (1 - P2 )• 1 - rV-(1 - r)V
(1 - P )*(1 - r )*(1 - в )*(1 - P2 )* r*V* (1 - r )V +(1 - P )*(1 - r )* в.
Легко показать, что Р^К + РрК + РЛк + Рно = 1 ■
На рис. 2 приведен фрагмент вероятностно-логического графа алгоритма В, который содержит отличия от алгоритма А.
Рис. 2. Фрагмент графа алгоритма полуавтоматического исправления ІБвИ 1028-9763.Математичні машини і системи, 2007, № 1
Здесь приняты следующие дополнительные обозначения:
Sm и Sm - соответственно ошибка идентифицирована и не идентифицирована среди т синонимов.
Таким образом, имеем следующие вероятностные оценки:
PS- = Р ; (4)
РЩк =(1 - P)(1 - г )(1 -Р)-Р pm) ; (5)
Ррк ’ =(1 - Р)-(1 - г )-(1 - в) -{Рг (1 - П( т))+(1 - Рг )}; (6)
РЛК =(1 - Р)-(1 - г ) -Р (7)
и соответственно РК1 + PZ + Pi& + Kï + С = 1.
Вероятность п(т) равна [3]:
П(т)= ^.С^ч-г!-{1-г/4&-1 + т8(1 - г/-8-1 . (8)
¥ = Р ¥ + Р ¥ + Р ¥ (9)
Алгоритм А
Очевидно, ¥(аа> = 0. Далее, предполагая, что при полностью ручном исправлении
пользователь в среднем «обрабатывает» половину символов слова, положим РРК = ^ . Алгоритм В
Оценим величины РРК"1 и РП^К для максимального значения т = г, где г - полное количество синонимов. При ручном исправлении пользователю приходится отвергнуть все г
синонимов и в среднем обработать п/ символов, т.е. > = г + п/ , так как в этом случае все
/2 РК /2
синонимы образуются в результате исключительно случайных совпадений:
рРВ ’=£«р(«.г.у)+п=&V+2. <1°>
Я=о 2 2
При полуавтоматическом исправлении ошибка принадлежит Е , и, следовательно, один из
синонимов заведомо совпадает с Т, т.е. является не случайным. Поэтому, с учетом предыдущих
рассуждений,
КАК = 1 +1 ^+т р(8-г-у) = 1 +1Г (V -1). (11)
Рассмотрим результаты приложения моделей к совместному использованию помехоустойчивого удлиненного кода Рида-Соломона [1] и метода анализа обратных вариаций.
Рассматриваемый код является одним из кодов над полем Галуа ОЕ(рт) , где р - целое. Длина кода пи + пк = р +1, пк = 2.
В примере, приведенном в [1] для иллюстрации алгоритмов формирования и
декодирования кода, р = 11, исходное информационное слово Ап = 2500000001; контрольные
символы ат = 3,апо = 0; закодированное слово А„_„, = 25000000130. Здесь значения
информационных символов подобраны так, чтобы при вычислении избыточных символов не выйти за пределы десятичного алфавита. В общем случае, конечно, избыточные символы могут принимать одно из р значений и, следовательно, должны представляться (или могут интерпретироваться) как числа в системе счисления с основанием р . В данном примере это должно быть 11-ричное (или 16-ричное) основание. В связи с этим отметим, что двухразрядное число в системе счисления с основанием р < 33 можно представить трехразрядным десятичным
числом, т.к. 332 < 103 < 342. Поэтому для р < 33 два избыточных символа в алфавите р можно заменить тремя десятичными цифрами. Например, для р =11, пару значений а01 = 10 и а02 = 07 можно интерпретировать как двухразрядное 11-ричное число 10/07, десятичный эквивалент которого равен 117. Таким образом, для цифрового кода (ч = 10) может быть принято р = 31 при трех реальных избыточных символах и двух виртуальных (при соответствующем усложнении алгоритмов декодирования). Аналогичные рассуждения применимы и к другим q, р.
Описанный код полностью обнаруживает и исправляет однократные транскрипции.
Примем Е = {Е1, Е2, Е3, Е4, Е5, Е6} ; смысл классов ошибок и значений связанных с ними
параметров приведен в табл. 1.
Таблица 1. Классы ошибок
Класс ошибок Ег Характер ошибок Вероятность появления, рг [4] Количество генерируемых вариаций
Е1 Однократные транскрипции 0,5557 ^ -1)-п
е2 Вставка символа 0,1567 п
Е3 Выпадение символа 0,1204 q■ (п +1)
Е 4 Транспозиция соседних симвопов 0,0664 п -1
Е5 Двукратные транскрипции 0,0322 (Ч -1)2 < - п +1
Е6 Многократные ошибки 0,0686 Для рассматриваемого кода Е1. = Е 2к = {Е1}.
Результаты иллюстративных расчетов для моделей автоматического (алгоритм А) и полуавтоматического (алгоритм В) исправления приведены в табл. 2 и 3 соответственно. Сводная таблица результатов, отражающая вероятностные характеристики вариантов декодирования и соответствующие показатели трудоемкости для значения г = 0,001, q = 37,п = 10 , приведена в табл. 4. В данных табл. 4 учтено, что для варианта декодирования, ограниченного рассматриваемым кодом, как видно из рис. 1, РАК = Р1; РРК = 1 - Р1; РРК = (1 - Р1)(1 - г)(1 -5) ;
Рлк = (1 - Р)(1 - г )5; Р = Ррк 2.
При расчетах принято Е21 = {Е4} Е^ = {Е2,Е3,Е4}; ¡5 = г при допущении о
псевдослучайном характере распределения результатов декодирования кода, искаженного ошибкой, не принадлежащей к Е. = {Е1}.
Таблица 2. Иллюстративные расчеты для алгоритма А
е 2 г = 0,001, q = 10, п = 10 г = 0,001, q = 37, п = 10
Р 1 АК Р 1 РК Р 1 ЛК Р 1 АК Р 1 РК Р 1 ЛК
Е 21 0,62144 0,37431 0,0038077 0,62144 0,37431 0,0038077
Е 22 0,85731 0,13040 0,011850 0,77977 0,19136 0,028427
Таблица 3. Иллюстративные расчеты для алгоритма В
т Е 2 РАК = 0,55570, Рлк = 0,001, г = 0,001, q = 10, п = 10 РАК = 0,55570, РЛК = 0,001, г = 0,001, q = 37, п = 10
Р 1 ПАК Р 1 РК Р(т) Р 1 ПАК Р 1 РК Р(т)
Е 22 0,32177 0,12164 0,93863 0,27926 0,16415 0,81461
Е 22 0,34194 0,10147 0,99746 0,33444 0,10897 0,97558
Е 22 0,34281 0,10060 1,0000 0,34274 0,10067 0,99980
Е 22 0,34289 0,10060 1,0000 0,34282 0,10060 1,0000
Таблица 4. Сводные характеристики алгоритмов
Алгоритм декодирования Е 2 р 1 АК р 1 ПАК р 1 РК р 1 ЛК
Код 0,5557 — 0,4434 0,0004 2,22
Код+ алгоритм А Е 21 0,6214 - 0,3743 0,0038 1,87
Е 22 0,7797 - 01913 0,0284 0,96
Код+алгоритм В Е 21 0,5557 0,6626 0,3771 0,0004 1,95
Е 22 0,5557 0,3428 0,1006 0,0004 0,96
зависимости от выбранного множества Е2, значение РАК может быть повышено от 0,5557 до
Соответственно значение показателя трудоемкости Г может быть уменьшено с 2,22 до
платить за снижение Г , остается за проектировщиком, можно предположить, что практически
использование алгоритма А может иметь смысл лишь для режима оТМте, когда подтверждение исправления затруднено.
целесообразным дополнение Е2 двукратными транскрипциями и/или специфическими ошибками иных классов, выходящих за рамки упрощенного перечня табл. 1.
например, [5] (Е1к ={Е1з Е4 }).
Дополнение помехозащитного кода с исправлением ошибок методом корректировки по виртуальному словарю допустимых слов позволяет улучшить корректирующие и трудоемкостные характеристики кода. Полученные соотношения (1) - (3) и (4) - (7) позволяют получить ориентировочные оценки, характеризующие результаты применения метода в зависимости от заданных условий и используемого алгоритма и принять соответствующие решения.
Рассмотренный подход может оказаться полезным при выборе решения о корректировке ошибок каналов связи и носителей информации.
СПИСОК ЛИТЕРАТУРЫ