Рахман П.А. Основы защиты данных от разрушения. Коды Рида-Соломона
Подождите немного. Документ загружается.
21
Рис. 3. СхемаалгоритмадекодированиякодаРида-Соломона(окончание)
32
Вычислениеполиномавеличиношибок:
r
xxxSx mod
Вычислениепроизводнойполиномалокаторов:
02mod,
2
1
12mod,
1
2
31
x
x
xx
Вычислениевеличиношибок
vv ,,
1
:
]255,1[,1
22
l
vl
l
u
l
u
v
l
Локаторыусловию
удовлетворяют?
Да
Нет
1
Формированиеполиномаискажений:
τ
l
l
u
x
l
vxE
1
Коррекцияошибоквполиномекадра
xExCxF и
преобразованиевисправленныйкадрF
Ошибкиуспешно
исправлены
Ошибокне
обнаружено
Ошибки
неисправимы
22
Примеркодированияидекодирования
ПустьимеетсяисходноеинформационноесообщениеХакер, состоящееиз 5
k
символов. Согласно8-битной ASCII кодировки, каждому символуможно сопоставить
соответствующийкодвдиапазонеот0 до255. Внашемслучаеисходноесообщение
M
будетвсоответствующихсимволамкодахвыглядетьтак:
Соответственно, полиноминформационногосообщениябудетвыглядетькак:
240229
2
234
3
224
4
213 xxxxxM
Допустим, мы хотим использоватькоды Рида-Соломонадляисправлениядо 2
t
искаженныхбайтов. Втакомслучаенампонадобится 42
tr избыточныхбайтов. Кроме
того, порождающийполиномбудетследующим:
116231
2
216
3
30
4
4
1
2
xxxx
i
i
xxg
Тогда при кодировании мы должны вычислить остаток от деления полинома
00
2
0
3
0
4
240
5
229
6
234
7
224
8
213
4
xxxxxxxxxxM на полином
xg . Врезультатеделенияполучимостаток:
22881
2
61
3
5 xxxxR .
Послеэтого, сложивполученныйостатокс
4
xxM , получаемполиномкадра:
22881
2
61
3
5
4
240
5
229
6
234
7
224
8
213 xxxxxxxxxF
И, наконец, тогдарезультирующийкадр
F
длины 9
rkn будетследующим:
Теперь, допустим, припередачекадрапоканалусвязиилиприхранениинаносителе
вкадреисказилисьдвабайтаиврезультате(приприемекадраизканалаилисчитываниис
носителя), мыполучилиследующийискаженныйкадрC :
ЕслипреобразуеминформационныебайтыпотаблицеASCII кодировки, тоувидим,
чтополучаетсясловоЛамер– это, вобщем-то, словоспротивоположнымзначением, итот,
ктополучитэтосообщение, будетиспытывать, совсеминыечувства, чеммыожидали.
Чтоже, попробуемдекодироватьполученныйкадр. Итак, вполиномиальном виде
полученныйкадрвыглядитследующимобразом:
22881
2
61
3
5
4
240
5
229
6
236
7
224
8
203 xxxxxxxxxC
Вычислимкоэффициентысиндрома:
213228
4
281
8
261
12
25
16
2240
20
2229
24
2236
28
2224
32
2203)
4
2(
4
255228
3
281
6
261
9
25
12
2240
15
2229
18
2236
21
2224
24
2203)
3
2(
3
207228
2
281
4
261
6
25
8
2240
10
2229
12
2236
14
2224
16
2203)
2
2(
2
246228
1
281
2
261
3
25
4
2240
5
2229
6
2236
7
2224
8
2203)
1
2(
1
CS
CS
CS
CS
Таким образом, 213
4
,255
3
,207
2
,246
1
SSSS , коэффициенты синдрома
ненулевые, ивтом, чтоимеломестобытьискажение, сомневатьсянеприходится. Однако,
скольковдействительностибайтовискажено, наэтапедекодированияникогданеизвестно.
213 240229234224
213 240229234224 22881615
203 240229236224 22881615
23
Попытаемсянайтиполиномлокаторов
x поалгоритмуБерлекэмпа-Месси, итем
самым, такжеузнатьпредполагаемоеколичество
искаженныхбайтов.
Инициализацияалгоритма:
1x , 0
q , 1
m , 0
L ,
xxB
Итерация 0
q : вычисляем невязку
0
0
100
i
i
S
i
=
10
S = 2462461
.
Невязканенулевая, поэтомувычисляем )(
*
x = )(
0
)( xBx = 1246
x . Далее,
так как условие 10)1(00
mqL выполняется, то проводятся
следующие действия: 1)1(0
*
mqL , 000
Lqm ,
1
*
L
L
,
2111
1
246)(
1
0
)(
xxB . Послеэтоговыполняется 1246)(
*
)( xxx
и 0211)()(
xxBxxB . После этого, поскольку 4211
tqq , то
переходимкследующейитерации.
Итерация 1
q : вычисляем невязку
1
0
111
i
i
S
i
=
2011
SS =
1082071246246
. Невязка ненулевая, поэтому вычисляем
)(
1
)()(
*
xBxx = )0211(108)1246(
xx = 1202
x . Далее, таккак
условие 11011
mqL невыполняется, топереходим квыполнению
действий 1202)(
*
)( xxx и 00
2
211)()( xxxBxxB . Послеэтого,
поскольку 4221
tqq , топереходимкследующейитерации.
Итерация 2
q : вычисляемневязку
2
0
122
i
i
S
i
=
302112
SSS =
16025512072022460
. Невязка ненулевая, поэтому вычисляем
)(
2
)()(
*
xBxx = )00
2
211(160)1202( xxx = 1202
2
158 xx .
Далее, таккак условие 21021
mqL выполняется, то проводятся
следующие действия: 202
*
mqL , 112
Lqm ,
2
*
L
L
,
2845)1202(
1
160)(
1
2
)(
xxxxB . После этого выполняется
1202
2
158)(
*
)( xxxx и 028
2
45)()( xxxBxxB . Послеэтого,
поскольку 4231
tqq , топереходимкследующейитерации.
Итерация 3
q : невязка
3
0
133
i
i
S
i
=
40312213
SSSS =
752132552022071582460
. Невязка ненулевая, поэтому вычисляем
)(
3
)()(
*
xBxx = )028
2
45(75)1202
2
158( xxxx =
193
2
19 xx . Далее, так как условие 22132
mqL не
выполняется, топереходимквыполнениюдействий 193
2
19)(
*
)( xxxx
и 00
2
211)()( xxxBxxB . Послеэтого, поскольку )42()41(
tqq ,
топереходимкследующейитерации, товыходимизциклаитераций.
Посколькустепеньполиномалокаторов 2)193
2
19)(deg( xxx , такжекаки
2
L
, тосчитается, чтополиномалокаторовуспешнонайденным.
24
Таким образом, мы успешнонашлиполиномалокаторов 193
2
19)( xxx
минимальнойстепени, ичтоболееважно, егостепень, равная2, иестьпредполагаемое
количествоискаженныхбайт, тоесть, инымисловами, 2
.
Теперь, путемполногопереборазначений
255
2,,
1
2 и, подставляякаждоеизнихв
полиномлокаторов, находимкорни, вкоторыхполиномлокаторовобращаетсявнуль. Этими
корнями, являются элементы
247
2
1
2
u
и
249
2
2
2
u
, тогда учитывая, что
uu
255
2
2
при 2550
u , получаем, наконец, искомыелокаторыошибок:
8
1
u и 6
2
u
Примечание. Мылегкоможемпроверитькорни, подставивихвполиномлокаторов:
01)
247
2(93
2
)
247
2(19)( x и 01)
249
2(93
2
)
249
2(19)( x
Теперь вычислим полином величин ошибок:
r
xxxSx mod =
4
mod)193
2
19()246207
2
255
3
213( xxxxxx =
4
mod246181
2
0
3
0
4
165
5
179 xxxxxx = 246181
x
Такжевычислимформальнуюпроизводнуюполиномалокатора:
93
1
02mod,
2
1
12mod,
1
2
31
x
x
xx
Теперьужеможновычислитьсамивеличиныошибок:
693)246
249
2181(
2
2
2
2
2
3093)246
247
2181(
1
2
1
2
1
uu
v
uu
v
Тогда, окончательно, получаемпредполагаемыйполиномискажений:
6
6
8
30
2
2
1
1
2
1
xx
u
xv
u
xv
l
l
u
x
l
vxE
Остаетсятолькосложитьполиномискаженногокадрасполиномомискажений:
22881
2
61
3
5
4
240
5
229
6
234
7
224
8
213)(
00
2
0
3
0
4
0
5
0
6
6
7
0
8
30)(
22881
2
61
3
5
4
240
5
229
6
236
7
224
8
203
xxxxxxxxxF
xxxxxxxxxE
xxxxxxxxxC
Наконец, послепреобразованияполиномавкадримеем:
Чтоже, каквидимисправленныйкадр, полностью совпадаетскадром, которыйбыл
переданпосети(записаннаноситель). Такимобразом, исправлениепрошлоуспешно.
213 240229234224 22881615
25
Упрощенныйспособдекодированияприисправлениитолькоодиночныхошибок
Какмывидим, процедурадекодированиявобщемслучаевыполняетсядостаточно
сложным инетривиальнымспособом. Аппаратнаяреализацияалгоритмовкодированияи
декодированиядляобщегослучаятребует, какминимум, микроЭВМ спрошитымивПЗУ
всеминеобходимымиалгоритмами, атакжеспрямымиобратнымполямиГалуа.
Однако, при реализации алгоритмадекодирования частного случая 1
t , когда
закладываетсявозможностьисправлениятольколишьодиночныхошибок, алгоритмпоиска
иисправленияошибкиможносущественноупростить. Следуетзаметить, чтоалгоритм
кодирования, ипроцедуравычислениясиндромаошибкинапервомшагедекодированияне
упрощаются, иостаютсятакимиже, какидляобщегослучая.
При 1
t , избыточностьсоставляетвсего
2
r
байта. Порождающийполиномпри
этом:
86
2
2
1
2
xx
i
i
xxg
. Кодированиенекоторогосообщения
M
длиною k
байтов, даеткадрдлиною 2
kn байтов:
Допустим, врезультатеискажениямыимеемнекоторыйпринятыйизсети(считанный
сносителя) кадрC длиною 2
kn байтов.
Поскольку
2
r
, то, подставляявсоответствующийемуполином )(xC значения
1
2
и
2
2
, мы получаем два коэффициента синдрома )
1
2(
1
CS и )
2
2(
2
CS . Если оба
коэффициентанулевые 0
2
1
SS , тосчитается, чтоошибокнет.
Предположимтеперь, чтоимеломестобытьискажение, причемколичествоошибок
неизвестно. Ключеваязадачадекодированиявобщемслучаевыглядит:
)(
21
min)(deg
1
x
tj
x
i
ij
S
ij
S
Однако, соднойстороны 1
t , сдругойстороны минимальнаякратностьошибки
1
, итогдаиндексзаключенвпределы 22
j . Тогдасистемаупрощаетсядоодного
уравненияприиндексе 2
j :
1
22
i
i
S
i
S . Крометого, унасвсегодвакоэффициента
синдрома
1
S и
2
S , ипри 2
j , имеемдопустимоеслагаемое
1
1
S , толькопри 1
i . В
итоге, ключеваясистемауравненийупрощаетсядовида
1
1
2
SS , откудалегкополучаем,
коэффициентполиномалокатора
1
2
1
SS , итогдапосколькувполиномелокатора
младшийкоэффициент 1
0
поопределению, товитогеимеемполиномлокаторов:
1
1
2
)( xSSx
M
k – 1
… M
0
R
1
R
0
С
n – 1
… C
0
26
Таким образом, 1
t , мы решаем ключевую задачудекодирования, неприменяя
сложноговреализацииалгоритмаБерлекэмпа-Месси.
Примечание. Важноотметить, чтовтакомслучаемыавтоматическипредполагаем,
чтопроизошлатолькоодиночнаяошибка 1
, но, имеявсегодвакоэффициентасиндрома
ничегобольшегоинельзясделать. Вслучае, еслидействительноеколичествоискажений
будетбольшеодной 1
, декодирование, разумеется, будетработатьнекорректно.
Нетрудновидеть, чтополиномлокаторовимеетединственныйкорень
2
1
2 SS
u
,
откудалегкополучаемсамлокаторошибки:
1
2
log
2
2
log
1
2
2
log
12
2
21
2
SSSSu
SS
u
SS
u
Тогда, учитывая, чтовычислениелогарифмапооснованиюпримитивногоэлемента2
вполеГалуа )
8
2(GF , можновыполнять, простосчитываясоответствующийэлементиз
обратногополяГалуа )
8
2(
1
GF . Такимобразом, вычислениелокатораошибкисводитсяк
простому извлечению элементов ]
2
[
1
SGF
и ]
1
[
1
SGF
обратного поля Галуа и
вычислению разности междуними(постандартным правилам традиционнойалгебры).
Напомним, чтодлявычисленияразностистепенейдействуетправило, чтоеслиразность
степенейменьшенуля, токнейприбавляется255.
Полиномлокатораобязательноследуетпроверитьнаусловие ]10[
nu , иесли
условиенесоблюдается, томожноговоритьотом, чтодекодированиепрошлонекорректно
и, очевидно, имеломестобытьискажениебольшегочислабайтов 1
.
Вычислим теперь полином величин ошибок:
)mod(
r
xxxSx =
)
2
mod(1
1
2
1
2
xxSSSxS =
)
2
mod(
11212
2
1
2
2
xSxSSSSxSS
=
)
2
mod(
122
2
1
2
2
xSxSSxSS
= )
2
mod(
1
2
1
2
2
xSxSS
=
1
S .
Вычислимтеперьпроизводнуюполиномалокаторов, учитываячто 1
:
121
02mod,
2
1
12mod,
1
2
31
SS
x
x
xx
Наконец, можновычислитьвеличинуошибку:
2
2
1121
22 SSSSS
uu
v
Выполнимследующиепреобразованияполученнойформулы:
2
2
1
SSv =
2
2
12
log
2
SS
=
22
log
12
log2
2
SS
Таким образом, вычислениевеличины ошибки сводитсякпростомуизвлечению
элементов ]
1
[
1
SGF
и ]
2
[
1
SGF
, ивычислениюразности ]
2
[
1
]
1
[
1
2 SGFSGF
. Если
привычислении ]
1
[
1
2 SGF
результатбольше255, тоотрезультатавычисляетсяостаток
помодулю 255. Крометого, еслиразностьменьшенуля, токнейдобавляется255. После
этогонеобходимовозвестипримитивныйэлемент2 вполученную разность, вполеГалуа
)
8
2(GF – этоделаетсяизвлечениемсоответствующегоэлементаизосновногополя )
8
2(GF .
27
5. Вероятностныйанализискажений. Выборкратностиисправляемыхошибок.
Дляканаловпередачиданных, какправило, задаетсяоценкавероятностиискажения
бита, посколькуданныепередаютсяввидепоследовательногопотокабитов, икаждыйиз
нихможетподвергнутьсяискажению. Сточкизренияискажениявсебиты«равноправны», и
неимеетзначениято, ккакомубайту, словуит.п. принадлежитбит. Вслучаеискажения
несколькихбитов, последниемогутразличнымиспособамирасполагатьсявнутрикадра,
состоящегоиз
n
байтов, например, 8 искаженныхбитовмогут«уместиться» внутриодного
байта, амогут«распылиться» по8 различным байтам – иэтобудутпринципиально
различныеситуациисточкизрениякорректирующейспособностикодовРида-Соломона.
Чтобыоцениватьвероятностиискаженияодного, несколькихиливсехбайтоввкадре
наосновеинформацииобазовойвероятностиискаженияодногобитамыдолжныобратиться
кматематическомуаппаратутеориивероятностей[10].
Пусть,
p
– базоваявероятностьискаженияодиночногобита(вканалепередачи
данныхиливносителеинформации).
Согласнотеориивероятностейвероятностьтого, чтоисказитсябайт, равнавеличине,
дополнительной(доединицы) квероятноститого, чтониодинбитвбайтенеисказится:
8
11 p
Byte
P
Тогда, согласнобиномиальному распределению Бернулли, получаем вероятность
того, чтоисказитсяровно
байтоввкадре, состоящегоиз
n
байтов, призаданной
вероятности
p
искаженияодногобита:
)(
8
1
8
11)(
n
pp
n
CP
Искаженныебитымогут«попадать» вкакие-тобайты, авкакие-то«непопадать».
Формулаопределяетвероятностьискажения
байтов, приусловиицелостностиостальных
n байтов, вовсехподходящихвариантахискажения
8
битов, приусловии
целостностиостальных
n8 битоввкадреиусловии, чтовкаждыйиз
байтов«попадет»
хотябы одинискаженныйбитвкаждом варианте, итакжеучитываютсявсесочетания
искаженных
байтовпо
n
байтамвкадре.
Наконец, вероятностьтого, чтоисказитсянеболее
t
байтоввкадредлиною
n
байтов,
призаданнойвероятности
p
искаженияодногобита:
t n
pp
n
CtP
0
)(
8
1
8
11)(
Следуетособоотметить, чтоможетвозникнутьложнаяиллюзия, чтовероятность
ошибок большей кратности (искажения большего числабайтов), обязательно меньше
вероятностиошибокменьшейкратности(искаженияменьшегочислабайтов). Например,
иллюзияотом, чтоискажениедвухбайтовкудаменеевероятно, чемискажениеодного
байта. Вдействительностиже, всезависитотбазовойвероятностиискаженияодногобитаи
количествабайтоввкадре, иприбольшойбазовойвероятностиискажениябитаибольшой
длинекадра, ошибкабольшейкратностиможетбытькудаболеевероятна, чем ошибка
меньшейкратности. Этонесложнопояснить: прибольшойвероятностиискажениябитаи
большой длинекадра, среднее количество искаженных битовможетбыть настолько
большим, чтоонипросто«неумещаются», ниводном, нивдвух, нидажевбольшемчисле
байтов, иискажаютбольшоеколичествобайтоввкадреиименноэтонаиболеевероятно.
Этот«эффект» наглядновиденнаграфиках(рис. 4) зависимостейвероятностиискажения
ровно
байтовприразличныхзначенияхбазовойвероятности
p
искажениябита.
28
Рис. 4. Графикизависимостейвероятностиискаженияровнобайтоввкадре
длиноюn = 20 байтовприразличнойбазовойвероятностиp искажениябита.
Каквидноизграфиков, толькопридостаточномалойбазовойвероятностиискажения
битапризаданнойдлинекадраможноговорить, чтоошибкибольшейкратностименее
вероятны, чемошибкименьшейкратности. Сростомбазовойвероятностиискажениябита,
ситуация меняется, и наблюдаютсяслучаи, когданаиболее вероятны ошибки строго
конкретнойкратности, причемдалеконеодиночной, итакдалее, вплотьдокрайнегослучая,
когданаиболеевероятноискажениевсехбайтоввкадре.
Оценим теперь вероятность искажения кадра длиною
n
байтов при условии
применениякодовРида-Соломонагарантированноисправляющих
t
искаженныхбайтовс
помощью tr 2
избыточныхбайтов. Надолю полезнойинформации, очевидно, вэтом
случаеостаетсялишь rnk
байтов. Привозникновенииошибоккратности
t
декодер
успешноисправитошибки, ине«справится» онтолькоприошибкахкратности
t
(при
t2
декодертакжегарантированнораспознаетошибку, нобезвозможностикоррекции).
Тогдавероятность«неисправимого» искажениякадрадлиною
n
байтовприусловии
применениякодовРида-Соломонас tr 2
избыточнымибайтамиопределяетсякак:
n
t
n
pp
n
CtP
1
)(
8
1
8
11)(
Нижеприведеныграфики(рис. 5) зависимостейвероятностиискажения
t
байтовв
кадредлиною
n
байтовприразличнойбазовойвероятности
p
искаженияодиночногобита.
29
Рис. 5. Графикизависимостейвероятностиискаженияболееt байтоввкадре
длиноюn = 20 байтовприразличнойбазовойвероятностиp искажениябита.
Каквидноизграфиков, вероятность«неисправимого» искажениякадрадлиною
n
байтовприусловии применениякодовРида-Соломонас tr 2
избыточными байтами
сильнозависитопятьжеотбазовойвероятностиискаженияодиночногобита. Причем, также
не будем забывать, что при использовании кодов Рида-Соломона за возможность
исправления
t
искаженныхбайтовприходитсяплатить tr 2
избыточнымибайтами, ив
условиях, когдаунасзаданафиксированнаядлина
n
кадра, надолю байтовполезной
информацииостаетсявсеменьшее rnk
числобайтов. Впределе, если
n
четноечисло,
кодыРида-Соломонамогутобеспечитьисправлениевплотьдо 2/nt
байтов, приэтомвсе
n
кадровуйдутподизбыточныебайты, таккак nntr
)2/(22 , приэтомнеостанется
ниодногобайтадляхраненияполезнойинформации, таккак 0
nnrnk .
ПоэтомуприпостановкевопросаоцелесообразностииспользованиякодовРида-
Соломонаивыборачислаизбыточныхбайтовследуетиметьвкачествеисходныхданных,
какминимум, следующиеданные:
n
– фиксированнаядлинакадравбайтах.
p
– базоваявероятностьискаженияодиночногобита.
min
k – требуемоеминимальноечислобайтовполезнойинформациивкадре.
max
P – заданнаяпредельнодопустимаявероятностьискажениякадра.
30
Далее, исходяизусловиячто, должно соблюдатьсятребованиепо допустимой
вероятности искажения кадра и требование на минимальное число байтов полезной
информациипопытатьсявыбратькратность
t
исправляемойошибки:
*
min
2
max
)(
t
ktn
PtP
Если, невозможно найти параметр
t
, удовлетворяющий обоим условиям, то,
очевидно, применениекодовРида-Соломонанецелесообразно. Крометого, еслисамапосебе
вероятностьискаженийлюбойкратностименьшезаданнойдопустимойграницы, тоесть
max
)0( PP
, топрименениекодовРида-Соломонатакженецелесообразно. Ниже(рис. 6)
приведенасхемаалгоритмадляоценкицелесообразностиприменениякодовРида-Соломона
ивыборакратностиисправляемойошибки.
Пример1. Заданадлинакадра 36
n байтов, минимальноечислобайтовполезной
информации 32
min
k , базовая вероятность искажения бита
4
105
p и предельно
допустимаявероятностьискажениякадра 001,0
max
P .
Рассчитаем сначала вероятность искажения кадра в исходных условиях без
использования кодов Рида-Соломона, иными словами рассчитаем вероятность
возникновенияошибоклюбойкратности:
13414,0)0(
P
Очевидно, чтовероятностьзначительновышедопустимойграницы 001,0
max
P .
Тогдапопробуемвыбратькратность
t
исправляемойошибки, исходяизусловий:
32236
001,0)(
t
tP
Очевидно, длязаданноготребуемогочислабайтовполезнойинформации, можно
рассматривать только два варианта 1
t и 2
t . В этих вариантах вероятности
«неисправимого» искажения кадра равны: 00918,0)1(
P и 000412,0)2(
P .
Очевидно, чтовариант 2
t , удовлетворяетобоимусловием. Соответственно, применение
кодовРида-Соломонацелесообразно, причемчислоизбыточныхбайтов 42
tr .
Пример2. Заданадлинакадра 128
n байтов, минимальноечислобайтовполезной
информации 120
min
k , базоваявероятность искажения бита
3
10
p и предельно
допустимаявероятностьискажениякадра 001,0
max
P .
Рассчитаем сначала вероятность искажения кадра в исходных условиях без
использования кодов Рида-Соломона, иными словами рассчитаем вероятность
возникновенияошибоклюбойкратности:
641,0)0(
P
Очевидно, вероятностьгораздовышезаданнойдопустимойграницы. Мыможемдля
сокращения перебора попробовать оценить вероятность «неисправимой» ошибки для
«крайнего варианта» 4
t , при котором еще соблюдается условие
120
min
120421282 ktn . Имеем, 0038,0)4(
P ивидим, чтодажев«крайнем
варианте», исправленияошибок вплотьдо 4-х кратных, вероятность«неисправимого»
искаженияпревышаетзаданную допустимую границу. Так, чтоприменениекодовРида-
Соломонавданномслучаенецелесообразно. Здесьтребуетсядляначалалибоуменьшить
длинукадра, либобазовуювероятностьискажениябита, либоитоидругое.