Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов
Описанная модель автоматического исправления ошибок основана на совместном применении кодовых методов и методаобратных искажений для повышения достоверности входной информации и снижения трудоемкости исправления ошибок.Рассматриваются комбинированные алгоритмы автоматической и полуавтоматической кор...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2007
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/822 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов / Литвинов В.А., Майстренко С.Я., Пилипенко Ю.Г. // Математические машины и системы. – 2007. – № 1.– С. 67 – 76. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-822 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-8222008-07-02T12:00:54Z Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов Литвинов, В.А. Майстренко, С.Я. Пилипенко, Ю.Г. Моделювання і управління великими системами Описанная модель автоматического исправления ошибок основана на совместном применении кодовых методов и методаобратных искажений для повышения достоверности входной информации и снижения трудоемкости исправления ошибок.Рассматриваются комбинированные алгоритмы автоматической и полуавтоматической коррекции ошибок. Дляпредлагаемых алгоритмов аналитически получены вероятностные оценки автоматической, полуавтоматической, ручной иложной коррекции, которые могут быть использованы при принятии решений относительно выбора алгоритмакорректировки. Табл.: 4. Ил.: 2. Библиогр.: 5 назв. Описана модель автоматичного виправлення помилок ґрунтується на сумісному використанні кодових методів та методузворотних спотворень для підвищення достовірності вхідної інформації й зниження трудомісткості виправлення помилок.Розглядаються комбіновані алгоритми автоматичної та напівавтоматичної корекції помилок. Для запропонованих алгоритміваналітично отримані імовірнісні оцінки автоматичної, напівавтоматичної, ручної та хибної корекції, які можутьвикористовуватись при прийнятті рішень відносно вибору алгоритму корекції. Табл.: 4. Іл.: 2. Бібліогр.: 5 назв. The described model of the automatic error correction is based on the joint application of the code methods and method of theinverse distortion for increasing validity of the input information and saving labor of error correction. The combined algorithms ofautomatic and semiautomatic error correction are considered. For the proposed algorithms, probabilistic estimations of theautomatic, semiautomatic, manual and false correction, which can be used while deciding which algorithm of adjustment to choose,are analytically derived. Tabl.: 4. Figs.: 2. Refs.: 5 titles. 2007 Article Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов / Литвинов В.А., Майстренко С.Я., Пилипенко Ю.Г. // Математические машины и системы. – 2007. – № 1.– С. 67 – 76. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/822 681.51:57 ru Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Литвинов, В.А. Майстренко, С.Я. Пилипенко, Ю.Г. Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| description |
Описанная модель автоматического исправления ошибок основана на совместном применении кодовых методов и методаобратных искажений для повышения достоверности входной информации и снижения трудоемкости исправления ошибок.Рассматриваются комбинированные алгоритмы автоматической и полуавтоматической коррекции ошибок. Дляпредлагаемых алгоритмов аналитически получены вероятностные оценки автоматической, полуавтоматической, ручной иложной коррекции, которые могут быть использованы при принятии решений относительно выбора алгоритмакорректировки. Табл.: 4. Ил.: 2. Библиогр.: 5 назв. |
| format |
Article |
| author |
Литвинов, В.А. Майстренко, С.Я. Пилипенко, Ю.Г. |
| author_facet |
Литвинов, В.А. Майстренко, С.Я. Пилипенко, Ю.Г. |
| author_sort |
Литвинов, В.А. |
| title |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| title_short |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| title_full |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| title_fullStr |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| title_full_unstemmed |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| title_sort |
исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2007 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/822 |
| citation_txt |
Исправление ошибок пользователя на основе совместного применения помехозащитных кодов и виртуального словаря допустимых слов / Литвинов В.А., Майстренко С.Я., Пилипенко Ю.Г. // Математические машины и системы. – 2007. – № 1.– С. 67 – 76. |
| work_keys_str_mv |
AT litvinovva ispravlenieošibokpolʹzovatelânaosnovesovmestnogoprimeneniâpomehozaŝitnyhkodovivirtualʹnogoslovarâdopustimyhslov AT majstrenkosâ ispravlenieošibokpolʹzovatelânaosnovesovmestnogoprimeneniâpomehozaŝitnyhkodovivirtualʹnogoslovarâdopustimyhslov AT pilipenkoûg ispravlenieošibokpolʹzovatelânaosnovesovmestnogoprimeneniâpomehozaŝitnyhkodovivirtualʹnogoslovarâdopustimyhslov |
| first_indexed |
2025-07-02T04:27:22Z |
| last_indexed |
2025-07-02T04:27:22Z |
| _version_ |
1836507927659151360 |
| fulltext |
ISSN 1028-9763.Математичні машини і системи, 2007, № 1
67
УДК 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.
Key words: user errors, automatic correction, data reliability, error-correcting coding.
Анотація: Описана модель автоматичного виправлення помилок ґрунтується на сумісному використанні
кодових методів та методу зворотних спотворень для підвищення достовірності вхідної інформації й
зниження трудомісткості виправлення помилок. Розглядаються комбіновані алгоритми автоматичної та
напівавтоматичної корекції помилок. Для запропонованих алгоритмів аналітично отримані ймовірнісні
оцінки автоматичної, напівавтоматичної, ручної та хибної корекції, які можуть використовуватись при
прийнятті рішень відносно вибору алгоритму корекції.
Ключові слова: помилки користувача, автоматична корекція, достовірність даних, перешкодозахисні коди.
Аннотация: Описанная модель автоматического исправления ошибок основана на совместном
применении кодовых методов и метода обратных искажений для повышения достоверности входной
информации и снижения трудоемкости исправления ошибок. Рассматриваются комбинированные
алгоритмы автоматической и полуавтоматической коррекции ошибок. Для предлагаемых алгоритмов
аналитически получены вероятностные оценки автоматической, полуавтоматической, ручной и ложной
коррекции, которые могут быть использованы при принятии решений относительно выбора алгоритма
корректировки.
Ключевые слова: ошибки пользователя, автоматическая коррекция, достоверность данных,
помехозащитные коды.
1. Введение
Известны и описаны в литературе методы помехозащитного кодирования, предназначенные для
повышения достоверности входной алфавитно-цифровой информации путем автоматического
исправления ошибок пользователя. Наиболее полный обзор таких методов приведен в [1].
Большинство этих методов ориентировано на автоматическое исправление однократных ошибок
типа замены значения одного символа и обнаружение с последующим «ручным» исправлением
ошибок иных классов.
Помехозащитные коды с исправлением ошибок (КИО) применяются для защиты
информации в каналах связи, где вероятность появления ошибок, кратности более 1, значительно,
на несколько порядков меньше вероятности однократной ошибки. Поэтому относительное
количество не автоматически исправленных ошибок сравнительно невелико. Для информации,
вводимой пользователем, положение иное. Здесь, как известно, ошибки типа, например, пропуска
символа имеют кратность от 1 до n в зависимости от позиции пропущенного символа, а
вероятность такой ошибки не намного меньше вероятности однократной транскрипции. По этим
причинам относительное количество вручную исправляемых ошибок здесь может быть
значительным.
Метод, позволяющий в этих случаях уменьшить долю ошибок, исправляемых вручную, и
снизить тем самым общую трудоемкость ввода и корректировки информации, заключается в
расширении штатной процедуры декодирования КИО за счет привлечения метода обратных
искажений («вариаций» ошибочного слова) и проверки корректности значения вариации по
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 68
словарю допустимых слов [2]. При отсутствии реального словаря в качестве такового может быть
использован виртуальный словарь (см. далее).
В статье решается задача построения модели и оценки существенных характеристик
метода.
2. Постановка задачи и алгоритм декодирования и исправления ошибок
Введем следующие обозначения и допущения:
ku nnq ,, – соответственно алфавит, количество информационных символов, количество
контрольных символов входного слова, nnn ku =+ ;
{ }iE=E – множество классов возможных ошибок;
ip – относительное количество ошибок класса iE в потоке вводимых слов;
1
kE – подмножество классов ошибок, на автоматическое исправление которых
ориентирован конкретный КИО, и назовем их первично корректируемыми ошибками;
2
kE – подмножество классов ошибок, идентифицируемых виртуальным словарем (вторично
корректируемые ошибки);
T – виртуальный словарь – множество слов, удовлетворяющих условию отсутствия
ошибки, определенному контрольным соотношением (алгоритмом кодирования-декодирования)
используемого КИО. Мощность T не превышает nq ;
knq
r
1= – коэффициент избыточности кода, определяющий относительное количество
всевозможных комбинаций значений n символов, не удовлетворяющих условию вхождения в T .
Примем допущение, что значения вариаций ошибочного слова случайно распределены
среди nq всевозможных значений слов. В этом случае процесс генерации вариаций и их
сравнения с T мы можем описать моделью испытаний Бернулли, для которой вероятность
P(g,r,V) случайного совпадения в точности g вариаций из V проверяемых, при условии, что
вероятность одного случайного совпадения равна r определяется известной формулой
биноминального распределения:
gVgg
V VrCP(g,r,V) −= .
Общая схема комбинированной процедуры включает два этапа.
1. Декодирование слова (кода) стандартной процедурой, присущей используемому КИО.
1.1. Идентификация слова как правильного или ошибочного.
1.2. Если в слове имеется ошибка, принадлежащая множеству 1
kE , то она
обнаруживается и автоматически исправляется. Иначе, слово идентифицируется как неисправимо
ошибочное (в смысле возможностей кода). Переход к этапу 2.
ISSN 1028-9763.Математичні машини і системи, 2007, № 1
69
2. Генерация V вариаций в классах ошибок, принадлежащих множеству 2
kE , и проверка
каждой вариации слова на принадлежность T (т.е., по сути, многократное повторение этапа 1 для
генерируемых вариаций). В зависимости от результатов проверки возможно автоматическое или
полуавтоматическое исправление в соответствии с алгоритмами, описанными в [2].
При этом возможны следующие финальные исходы.
ПАКАК RR , – ошибка правильно идентифицирована и исправлена автоматически
(вероятность АКP ) или полуавтоматически, т.е. с подтверждением пользователя (вероятность
ПАКP );
РКR – идентифицировать ошибку не удается и она исправляется полностью „вручную”
(вероятность РКP );
ЛКR – ошибка идентифицирована неверно и исправлена ложно (вероятность ЛКP ).
Определение этих вероятностей и является целью построения следующих моделей. Под
вероятностями здесь и далее понимается относительное количество исходов, “благоприятных” в
определенном конкретном смысле.
3. Общая модель
3.1. Вероятностные характеристики метода (значения АКP , РКP ,
ЛК
P ) для автоматической
вторичной корректировки (алгоритм А) определяет вероятностно-логический граф, приведенный
на рис. 1. За основу принят алгоритм однозначной корректировки вторично корректируемой ошибки
[2]. В этом случае автоматическое исправление ошибок 2
kE производится только при единственном
совпадении вариации со словарем (т.е. при отсутствии синонимов).
Последовательность x дуг графа означает совместное наступление x независимых
событий; финальная вероятность последнего события равна произведению вероятностей,
приписанных каждой дуге; разветвление y дуг означает наступление одного из y несовместных
событий; суммарная вероятность событий по y разветвляющимся дугам, равная сумме
соответствующих вероятностей, должна быть равна 1, как полная группа событий. Сумма
финальных вероятностей по листьям дерева должна быть равна 1, а для искомых вероятностей P
должны выполняться условия:
1=+++
НОЛКРКАК
PPPP ;
[ ]10,P,P,P,P
НОЛКРКАК
∈ .
Таким образом, приведенный граф отражает структуру финальных вероятностей
независимых событий.
На рис. 1 приняты следующие обозначения событий и их вероятностей:
0S – ошибка произошла;
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 70
1S – ошибка 1 kE∈ , вероятность этого события 1π равна относительному количеству
первично обнаруживаемых ошибок 1P ;
12 SS = – ошибка ∉ 1 kE с вероятностью 12 1 P−=π ;
21S – ошибка обнаружена с вероятностью r121 −=π ;
2122 SS = – ошибка не обнаружена с вероятностью r=22π ;
211S – ошибка принята для идентификации и исправления с вероятностью βπ −= 1211 ;
211212 SS = – ошибка ложно исправлена кодом с вероятностью βπ =212 ;
2111S – ошибка 2 kE∈ с вероятностью 22111 Pπ = ;
21112112 SS = – ошибка
2
k
E∉ с вероятностью 22112 1 P−=π ;
21111S – ошибка однозначна )1( =z с вероятностью ( ) 1
21111 1)1,,0( −−=−=π VrVrP ;
2111121112 SS = – ошибка многозначна ( 1>z ) с вероятностью
)V,r,(P
V
g
)V,r,g(P 101
1
1
1
21112
−−=∑
−
=
−=π ;
21121S – для ошибки, которая не принадлежит 2
kE , не состоялось ни одного случайного
совпадения вариаций со словом словаря )0( =z с вероятностью
( )VrrV,r,V)P( −−=−=π 111121121 ;
ЛKR
Рис. 1. Граф частных событий для алгоритма автоматического исправления
S0 1π
РКR
S21
S2 S22
АКR
2π
S1 22π
21π
S212
212π
S211
211π
S2111 S2112
2111π
2112π
S21111 S21112 S21121
S21122
21111π
21112π
21121π
21122π
ISSN 1028-9763.Математичні машини і системи, 2007, № 1
71
2112121122 SS = – ошибка, которая не принадлежит 2
kE , однозначна ( 1=z ) с вероятностью
( )VrrV)V,r,( −==π 11P
21122
.
С учетом приведенных обозначений и вида графа рис. 1 можно записать такие логические
выражения:
( );SSSSSSR
2111211212AK 211111
∧∧∧∧∨=
( ) ( ) ( )( );SSSSSSSR
211212РK 211212112211122111
∧∨∧∧∧∧=
( ) ( )( )212211222112211212ЛK SSSR SSS ∨∧∧∧∧= .
С учетом того, что все события на рис. 1 взаимно независимы, для вероятностей
ЛКРКАК
P,P,P можно записать
211111
ππππππ
2111211212АК
P ⋅⋅⋅⋅+= ;
( )
211212112211122111
πππππππ
211212РК
P ⋅+⋅⋅⋅⋅= ;
( )
212211222112
ππππππ
211212ЛК
P +⋅⋅⋅⋅= .
Окончательно имеем
( ) ( ) ( ) ( ) 1
211
1 1111 −−⋅−⋅−⋅−+= V)(
АК rPβrPPP ; (1)
( ) ( ) ( ) ( ) ( ) ( )
−⋅⋅−⋅−+
−−⋅−⋅−⋅−= − VV)(
РК rVrPrPβrPP 11111111 2
1
21
1 ; (2)
( ) ( ) ( ) ( ) ( ) ( ) ( ) βrPrVrPβrPP V)(
ЛК ⋅−⋅−+−⋅⋅⋅−⋅−⋅−⋅−= 1111111 121
1 . (3)
Легко показать, что 11111 =+++ )(
НО
)(
ЛК
)(
РК
)(
АК PPPP .
3.2. Полуавтоматическое исправление ошибок (алгоритм В) внешне (в смысле интерфейса
с пользователем) подобно алгоритму Spell-Checker’a текстового редактора (например, Word'а). При
отсутствии однозначности корректировки пользователю предлагается для подтверждения до m
вариантов исправлений. Если среди них нет правильного варианта, ошибка исправляется вручную.
В Word’е предлагаются все установленные возможные варианты исправления, что, впрочем, для
определенных классов ошибок тоже не освобождает от полностью ручного исправления.
На рис. 2 приведен фрагмент вероятностно-логического графа алгоритма В, который
содержит отличия от алгоритма А.
( )mS
(m)S
AKR ПAKR
РКR лкR
( )mπ
2111S 2112S ( )m-π1
Рис. 2. Фрагмент графа алгоритма полуавтоматического исправления
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 72
Здесь приняты следующие дополнительные обозначения:
mS и mS – соответственно ошибка идентифицирована и не идентифицирована среди
m синонимов.
Таким образом, имеем следующие вероятностные оценки:
1
)2( PPAK = ; (4)
( ) ( ) ( ) )(111 21
)2( mPrPPПАК π⋅β−⋅−⋅−= ; (5)
( ) ( ) ( ) ( )( ) ( ){ }221
2 11111 PmPβrPP π)(
РК −+−⋅−⋅−⋅−= ; (6)
( ) ( ) β⋅−⋅−= rPPЛК 11 1
)2( (7)
и соответственно 122222 =++++ )(
НО
)(
ЛК
)(
РК
)(
ПАК
)(
АК
PPPPP .
Вероятность ( )mπ равна [3]:
1
1
1
1
1
0
1 1
1
1 −−
−
−
=
−−
−
=
− −⋅⋅
+
+−⋅⋅= ∑∑ gVgg
V
V
mg
gVg
m
g
g
V r)(rC
g
m
r)( rC(m)π . (8)
3.3. Для дополнительной оценки эффективности алгоритмов автоматического и
полуавтоматического исправления введем понятие ориентировочной трудоемкости исправления
ошибок АКF , ПАКF , РКF и определим ее как среднее количество операций сравнения и нажатий
на клавиши, которые выполняет пользователь при соответствующих финальных исходах. Среднюю
трудоемкость F определим как взвешенную сумму:
F = AKP АКF + ПАКP ПАКF + РКP РКF . (9)
Алгоритм А
Очевидно, 0=)А(
АК
F . Далее, предполагая, что при полностью ручном исправлении
пользователь в среднем «обрабатывает» половину символов слова, положим 2
)( nF A
РК = .
Алгоритм В
Оценим величины )(В
РКF и )(В
ПАКF для максимального значения zm = , где z – полное
количество синонимов. При ручном исправлении пользователю приходится отвергнуть все z
синонимов и в среднем обработать 2
n символов, т.е. 2
nzF
)В(
РК
+= , так как в этом случае все
синонимы образуются в результате исключительно случайных совпадений:
22
n
rV
n
)V,r,g(gPF
V
og
)В(
РК
+=+=∑
=
. (10)
При полуавтоматическом исправлении ошибка принадлежит
2
k
E , и, следовательно, один из
синонимов заведомо совпадает с T , т.е. является не случайным. Поэтому, с учетом предыдущих
рассуждений,
ISSN 1028-9763.Математичні машини і системи, 2007, № 1
73
( )1
2
1
1
2
2
1
1
−+=++= ∑
−
=
Vr)V,r,g(P
g
F
V
og
)В(
ПАК
. (11)
4. Пример приложения моделей
Рассмотрим результаты приложения моделей к совместному использованию помехоустойчивого
удлиненного кода Рида-Соломона [1] и метода анализа обратных вариаций.
Рассматриваемый код является одним из кодов над полем Галуа )( mpGF , где p – целое.
Длина кода 1+=+ pnn
ku
, 2=kn .
В примере, приведенном в [1] для иллюстрации алгоритмов формирования и
декодирования кода, p = 11, исходное информационное слово ;2500000001=nA контрольные
символы ;a,a 03
0201
== закодированное слово .02500000013== knnA Здесь значения
информационных символов подобраны так, чтобы при вычислении избыточных символов не выйти
за пределы десятичного алфавита. В общем случае, конечно, избыточные символы могут
принимать одно из p значений и, следовательно, должны представляться (или могут
интерпретироваться) как числа в системе счисления с основанием p . В данном примере это
должно быть 11-ричное (или 16-ричное) основание. В связи с этим отметим, что двухразрядное
число в системе счисления с основанием 33p ≤ можно представить трехразрядным десятичным
числом, т.к. 233 < 310 < 234 . Поэтому для 33p ≤ два избыточных символа в алфавите p можно
заменить тремя десятичными цифрами. Например, для p =11, пару значений 1001 =α и 0702 =α
можно интерпретировать как двухразрядное 11-ричное число 10/07, десятичный эквивалент
которого равен 117. Таким образом, для цифрового кода ( )10=q может быть принято 31=p при
трех реальных избыточных символах и двух виртуальных (при соответствующем усложнении
алгоритмов декодирования). Аналогичные рассуждения применимы и к другим pq, .
Описанный код полностью обнаруживает и исправляет однократные транскрипции.
Примем E = { }654321 ,,,,, EEEEEE ; смысл классов ошибок и значений связанных с ними
параметров приведен в табл. 1.
Таблица 1. Классы ошибок
Класс
ошибок
iE
Характер ошибок Вероятность
появления,
ip [4]
Количество
генерируемых вариаций
1E Однократные транскрипции 0,5557 nq ⋅− )1(
2E Вставка символа 0,1567 n
3E Выпадение символа 0,1204 )1( +⋅ nq
4E Транспозиция соседних
символов
0,0664 1−n
5E Двукратные транскрипции 0,0322 1)1( 22 +−⋅− nCq n
6E Многократные ошибки 0,0686 –
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 74
Для рассматриваемого кода { } { }ikk EE == 2
1
1 ,EE .
Результаты иллюстративных расчетов для моделей автоматического (алгоритм А) и
полуавтоматического (алгоритм В) исправления приведены в табл. 2 и 3 соответственно. Сводная
таблица результатов, отражающая вероятностные характеристики вариантов декодирования и
соответствующие показатели трудоемкости для значения 10,37,001,0 === nqr , приведена в
табл. 4. В данных табл. 4 учтено, что для варианта декодирования, ограниченного
рассматриваемым кодом, как видно из рис. 1, 1PPАК = ; 11 PPРК −= ; )1)(1)(1( 1 β−−−= rPPРК ;
β−−= )1)(1( 1 rPPЛК ;
2
n
PF РК= .
При расчетах принято { } { }432
22
4
21 ,, EEEE kk == E ;E ; r=β при допущении о
псевдослучайном характере распределения результатов декодирования кода, искаженного
ошибкой, не принадлежащей к { }1
1 Ek =E .
Таблица 2. Иллюстративные расчеты для алгоритма А
10,10,001,0 === nqr 10,37,001,0 === nqr
2
kE
АКP РКP ЛКP
АКP РКP ЛКP
21
kE 0,62144 0,37431 0,0038077 0,62144 0,37431 0,0038077
22
kE 0,85731 0,13040 0,011850 0,77977 0,19136 0,028427
Таблица 3. Иллюстративные расчеты для алгоритма В
10,10,001,0
,001,0,55570,0
===
==
nqr
PP ЛКАК
10,37,001,0
,001,0,55570,0
===
==
nqr
PP ЛКАК
m
2
kE
ПАКP РКP )(mπ
ПАКP РКP )(mπ
21
kE 0,066003 0,37741 0,99601 0,066003 0,37741 0,99601
1 22
kE 0,32177 0,12164 0,93863 0,27926 0,16415 0,81461
21
kE 0,066267
0,37715
0,99999 0,066267 0,37715 0,99999
2 22
kE
0,34194
0,10147
0,99746 0,33444 0,10897 0,97558
21
kE 0,066267 0,37714 1,0000 0,066267 0,37714 1,0000
4 22
kE 0,34281 0,10060 1,0000 0,34274 0,10067 0,99980
21
kE 0,066267 0,37714 1,0000 0,066267 0,37714 1,0000
Z
22
kE 0,34289 0,10060 1,0000 0,34282 0,10060 1,0000
ISSN 1028-9763.Математичні машини і системи, 2007, № 1
75
Таблица 4. Сводные характеристики алгоритмов
Алгоритм
декодирования
2
kE АКP ПАКP РКP ЛКP F
Код 0,5557 – 0,4434 0,0004 2,22
21
kE 0,6214 – 0,3743 0,0038 1,87
Код+ алгоритм А
22
kE 0,7797 – 01913 0,0284 0,96
21
kE 0,5557 0,6626 0,3771 0,0004 1,95
Код+алгоритм В
22
kE 0,5557 0,3428 0,1006 0,0004 0,96
5. Анализ данных
1. Как видно из данных табл. 2, 4, комбинированная процедура декодирования анализом вариаций
ошибочного слова и автоматическим исправлением по виртуальному словарю позволяет повысить
относительное количество исправляемых ошибок и снизить трудоемкость ввода. Так, в
зависимости от выбранного множества 2
kE , значение АКP может быть повышено от 0,5557 до
0,7797 и более.
Соответственно значение показателя трудоемкости F может быть уменьшено с 2,22 до
0,96. Однако при этом повышается относительное количество ложно корректируемых ошибок. Хотя
окончательное решение относительно приемлемости цены (увеличение ЛКP ), которую стоит
платить за снижение F , остается за проектировщиком, можно предположить, что практически
использование алгоритма А может иметь смысл лишь для режима off-line, когда подтверждение
исправления затруднено.
2. Для полуавтоматического исправления (табл. 3, 4) доля ложно корректируемых ошибок не
увеличивается, а значение показателя суммарной трудоемкости F существенно снижается по
сравнению с чисто кодовой процедурой декодирования и исправления. При этом снижение
трудоемкости тем больше, чем больше классов ошибок включено в 2
kE . Поэтому может оказаться
целесообразным дополнение 2
kE двукратными транcкрипциями и/или специфическими ошибками
иных классов, выходящих за рамки упрощенного перечня табл. 1.
3. Сделанные заключения базируются на количественных результатах применения кода Рида-
Соломона ( { }1
1 Ek =E ), однако они качественно не меняются и при применении других кодов,
например, [5] ( { }41
1 , EEk =E ).
6. Выводы
Дополнение помехозащитного кода с исправлением ошибок методом корректировки по
виртуальному словарю допустимых слов позволяет улучшить корректирующие и трудоемкостные
характеристики кода. Полученные соотношения (1) – (3) и (4) – (7) позволяют получить
ориентировочные оценки, характеризующие результаты применения метода в зависимости от
заданных условий и используемого алгоритма и принять соответствующие решения.
ISSN 1028-9763.Математичні машини і системи, 2007, № 1 76
Рассмотренный подход может оказаться полезным при выборе решения о корректировке
ошибок каналов связи и носителей информации.
СПИСОК ЛИТЕРАТУРЫ
1. Бояринов И.М., Давыдов А.А. Мамедли Э.М., Смеркис Ю.Б. Использование помехоустойчивого кодирования
для защиты информации от ошибок оператора // АТ. – 1983. – № 2. – C. 5–48.
2. Кузьменко Г.Є., Литвинов В.А., Майстренко С.Я., Ходак В.І. Алгоритми і моделі автоматичної ідентифікації та
корекції типових помилок користувача на основі природної надмірності // Математичні машини і системи. –
2004. – № 2. – С. 134–148.
3. Литвинов В.А., Майстренко С.Я., Ступак Н.Б. Некоторые оценки вероятностных характеристик процесса
автоматической идентификации ошибок пользователя на основе эталонного словаря // УСиМ. – 2001. – № 2. –
C. 21–24.
4. Литвинов В.А., Крамаренко В.В. Контроль достоверности и восстановления информации в человеко-
машинных системах. – Киев: Техніка, 1986. – 200 с.
5. Sethi A.S., Rajaraman V., Kenjale P.S. An error-correcting coding shame for alphanumeric data // Information
Processing Letters. – 1988. – Vol. 7. – P. 72–77.
|