close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Исправление пакетов ошибок
циклическими кодами
Метод перемежения, коды Файра
Циклические коды
• Опр. Код C называется циклическим, если
(а ,а , … , а
) ∈ C ⇒ (а , а ,а , … , а
)∈C
• Замечание. Если С – циклический код, то вместе с
любым кодовым словом в С входят и все его
циклические сдвиги.
• Пример: С = {001, 010, 100}
Пакеты ошибок
• Опр. Пакет ошибок длины L – это область из
L подряд идущих разрядов, внутри которой
имеются ошибки (на границе области –
обязательно).
• Пример: е(х) = 00000110110100000 L = 7
• Если вектор е(х) является пакетом длины L,
дополненным нулями, то он имеет вид е(х) =
x b x , гдеdeg b x = L − 1.
• В приведенном примере: е(х) = x b x , где b(x)
= 1 + х +х +х + х
• Таким образом, b(x) описывает пакет ошибок,
x указываетначальныйлокаторпакета.
Циклический пакет ошибок
• Теорема. Если C — циклический (n, k)-код
над полем Fq, то C обнаруживает любой
пакет ошибок длины L ≤ n – k
• Следствие. Циклическим (n, k)-кодом
распознаётся и любой циклический сдвиг
пакета ошибок длины L ≤ n – k
(циклический пакет ошибок).
• Тогда е(х)=x b x - циклический пакет
ошибок , где deg b x ≤ L − 1иb ≠ 0
Разбиение пространства
на смежные классы
•
Пусть С⊆
- линейный код.
•
Тогда С⊲(
, +) – нормальная подгруппа.
•
⁄ - множество смежных классов по
Рассмотрим
аддитивной подгруппе С, а∈
a+ C = {a + x: x ∈ C}.
⁄ | и пусть С = а +С, С
Пусть m=|
классы, тогда по теореме Лагранжа:
1. ∀а: + =
.
2.
= ∐ ( + C).
3. m =
|
|
| |
=
=
, где = dim .
= а +С –все смежные
Синдром смежного класса
Теорема. Два вектора имеют одинаковый синдром тогда и
только тогда когда они содержатся в одном смежном
классе.
Доказательство.
1. У векторов из одного класса – одинаковые синдромы:
а, а′ ∈ С ⇒ =
+ x,x∈C ⇒Ha - Hа′ = H(a - a′) = Hx = 0.
2. Обратно, если Ha = Hа′, то 0 = Ha - Hа′ = H(a - a′)⇔ a - a′
∈C
Опр. Синдром смежного класса S (a + C) – синдром какоголибо его представителя.
Стандартное расположение
линейного кода
• Опр. Представитель смежного класса + C
называется лидером смежного класса. В качестве
лидера класса обычно выбирается вектор
наименьшего веса в классе.
• Опр. Стандартное расположение линейного кода
C — это таблица, в которой по строкам
располагаются элементы смежных классов + C,
лидер класса — в начале строки, первый столбец
— синдромы S( + C).
• Декодирование по таблице стандартного
расположения: для принятого вектора y
вычисляется синдром S(y) и сравнивается с
первым столбцом; вектор ошибок e — это лидер
класса ссиндромом S(y).
Пример таблицы стандартного
расположения
0 1
1 0 0 1 1
G=
⇒ H = 1 1
0 1 1 1 0
1 0
1 0
0 1
0 0
0
0
1
00→00000, 01 →01110, 10 → 10011, 11 → 11101.
000
001
010
100
110
011
101
111
00000
00001
00010
00100
01000
10000
11000
10100
10011
10010
10001
10111
11011
00011
01011
00111
01110
01111
01100
01010
00110
11110
10110
11010
11101
11100
11111
11001
10101
01101
00101
01001
Граница Рейгера
• Теорема (Граница Рейгера). Каждый
линейный блоковый код, исправляющий все
пакеты длиной L и менее, должен содержать,
по меньшей мере, 2L проверочных символов.
• Доказательство. Предположим, что код
исправляет все пакеты длины L и менее.⇒ он
не содержит в качестве кодового слова ни
одного пакета длины 2L и менее.
• Если а, а′ ∈С ⇒ а - а′ = x, х ∈ С.
Граница Рейгера
• Выберем 2 произвольных а и а′, все
компоненты, которых, кроме первых
2L, равны нулю.
• Если а, а′ ∈С ⇒ а - а′ = x, х ∈ С.
Однако, это разность – пакет длины 2L
и не может быть кодовым словом. ⇒ a
∈С ,а′ ∈С , где i ≠ j и | / | ≥ числа
таких различных векторов.
Граница Рейгера
• Всего векторов заданного вида
⇒
| / |≥
⇒ , должен содержать,
по меньшей мере, 2L проверочных
символов.
□
Некоторые циклические коды,
исправляющие пакеты ошибок
Порождающий многочлен
+
+
+
+
+
+
+
+
+1
+1
+
+
+1
+1
Параметры
Длина
исправляемого
пакета
(7, 3)
2
(15, 10)
2
(15, 9)
3
(511, 499)
4
Метод перемежения
• Чтобы из (n, k) – кода → (jn, jk) – код,
выберем из исходного кода j
произвольных кодовых слов и укрупним
кодовые слова, чередуя их символы. Если
исходный код исправляет произвольный
пакет ошибок длины L, то
результирующий будет исправлять все
пакеты ошибок длины jL.
Метод перемежения
•
•
Пример. (5, 2) – код → (10, 4) – код.
00000
0000000000
C= 01110
0010101000
10011
1000001010
11101
1010100010
0001010100
0011111100
1001011110
1011110110
0100000101
0110101101
1100001111
1110100111
0101010001
0111111001
1101011011
1111110011
C′
Метод перемежения для
циклических кодов
• Циклический (n, k) – кода → циклический (jn,
jk) – код
• Утв. Исходный код порождается многочленом
g(x), тогда порождающий многочлен
получаемого перемежением кода равен g(x ).
• Доказательство. Заметим, что перемежение
символов нескольких информационных
многочленов с последующим умножением на
g(x ) дает то же самое кодовое слово, что и
умножение каждого из исходных
информационных многочленов на g(x) с
последующим перемежением этих слов (n, k) –
кода.
Утв. Исходный код порождается многочленом
g(x), тогда порождающий многочлен
получаемого перемежением кода равен g(x ).
• Точнее, пусть
с x =i x g x ,
с x =i x g x ,
⋮
с x =i x g x - выбранные кодовые слова.
• Для формирования слов из кодаперемежения каждое из этих выбранных
информационных кодовых слов растягивается
вставкой между всеми символами слова j-1
нулей.
Утв. Исходный код порождается многочленом
g(x), тогда порождающий многочлен
получаемого перемежением кода равен g(x ).
• Кодовое слово из кода-перемежения
получается затем задержкой и
сложением этих слов:
c′(x) = с (x ) + xс (x ) + …+ x
= i x g x
+x
=[ i x + x i x
+xi x g x
i x g x =
+ ⋯+ x
с x
+ ⋯+
i x ]g x
=
Утв. Исходный код порождается многочленом
g(x), тогда порождающий многочлен
получаемого перемежением кода равен g(x ).
• с′(х) = i′(x)g x
Замена g х на g x эквивалентна
перемежению j копий кода,
порождаемого многочленом g(x).
□
Коды Файра
Параметры
Длина исправляемого пакета
(9, 4)
2
(35, 27)
3
(105, 94)
4
(279, 265)
5
(693, 676)
6
(1651, 1631)
7
(3825, 3802)
8
(8687, 8661)
9
(19437, 19408)
10
Коды Файра
• Опр. Кодом Файра называется исправлящий
пакеты ошибок циклический код на GF(q) с
порождающим многочленом
g(x) = (x
-1)p(x),
где p(x) – примитивный многочлен над GF(q), m
= deg p(x) ≥ L, где L – длина исправляемого
пакета, и который не делит x
-1.
• Длина кода Файра n равна наименьшему
целому n, такому, что g(x) делит x - 1
Коды Файра
• Теорема. Длина кода Файра n = е(2L 1), где е - наименьшее целое число,
такое, что p(x) делит x - 1.
Следовательно, если p(x) примитивен,
то для такого кода
n = ( - 1)(2L - 1)
k = ( - 1)(2L - 1) – m – 2L + 1
Теорема. Длина кода Файра n = е(2L - 1), где е - наименьшее целое
число, такое, что p(x) делит
− 1.Следовательно, если p(x)
примитивен, то для такого кода
=
− 1 2 − 1
= (
− 1)(2 − 1)– – 2 + 1
• Доказательство. При n = е(2L - 1)
возможно несколько разложений
многочлена x - 1:
(
)
− 1 = (x − 1) ∑
x ,
)
• x -1=x (
− 1 = (x
− 1) ∑
x(
• Т.к. р(х) делит x е - 1, то он делит и x - 1.
)
• Т.к. он не делит x (
-1, то он должен
)
делить многочлен ∑
x(
.
• x -1=x
)
Теорема. Длина кода Файра n = е(2L - 1), где е - наименьшее целое
число, такое, что p(x) делит
− 1. Следовательно, если p(x)
примитивен, то для такого кода
=
− 1 2 − 1
= (
− 1)(2 − 1)– – 2 + 1
• Таким образом,
x - 1 = (x
−1) р(х)а(х)
для некоторого а(х), и т.к. не существует меньшего
n, для которго имеет место это разложение, то такое
n равно длине кода.
• В часности, если р(х) – примитивный многочлен
степени m, то р(х) делит x − 1прие = - 1 и не
делит ни при каком меньшем значении е.
• deg g(x) = n - k ⇒k = n – deg g(x) =n – (deg p(x)+2L
1) =(
− 1)(2 − 1)– – 2 + 1
□
Коды Файра
• Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
• Доказательство. Код способен
исправлять все пакеты длины L и
менее, если никакие два таких пакета
(x) ,
(x) ∉ . В силу
цикличности кода без потерь общности
можно полагать, что i = 0.
Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
Предположим, что
•
(x) -
•
•
Многочлен x
•
• (x
(1)+(2):
x
•
•
x
(
− 1) р(х) (mod x - 1)(1)
(x) = а(х)(x
− 1 делит x
(
(x) ∈ . ⇒
(x) ,
)
(
(x) -
(
)[
− 1 для всех v ≥ 0 ⇒
− 1 ) (x) = Q(x)(x
)[
)
− 1) (mod x - 1)(2)
( )] = a′(x)(x
− 1) (mod x - 1)
(
)
(x) ( )] = a′′(x)(x
(mod x - 1). Для некоторых a′(x) и a′′(x).
− 1)
Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
• Пусть 0 ≤ v < e, такое что
на
• x
• x
(
, 0≤ k < L. ⇒
)
[ (x) (
)
[
(x) , будет умножаться
( )] = a′(x)(x
(x) -
− 1) (mod x - 1)
( )] = a′′(x)(x
− 1)
(mod x - 1), где deg (x) < L, deg (x) < L и k < L ⇒
• Степень многочлена в квадратных скобках не
превышает 2L-2. Но x
− 1 должен делить
стоящих в квадратных скобках многочлен. ⇒
Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
• Или
(x) -
(x) = 0
• Или
(x) (x) = 0
• По определению пакета ошибок оба
коэффициента
и
отличны от нуля.
⇒
• k = 0 или k = L – 1. В любом случае j =
v(2L-1) и (x) = (x) = b(x).
Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
• (1) приводится к виду:
)
-( (
− 1) ( ) = ( )(
− 1) ( )
• При v ≠ 0 многочлен р(х) не может
)
делить (
− 1, т.к. v < е и р(х) не
)
делит (
− 1 ни для одного целого
положительного v < е . ⇒ в левой части
равенства многочлен р(х) может
делить только b(x).
Теорема. Код Файра исправляет все
пакеты ошибок длины L и менее.
• Но deg b(x) < deg p(x) ⇒ при v ≠ 0 b(x) = 0.
• Т.к. j = v(2L – 1), то v = 0 означает, что j = 0, а
это совместно с уже доказанным равенством
=
противоречит выбору 2 разных
пакетов.
• Таким образом, 2 различных пакета
и
х
длины L и менее всегда принадлежат
разным смежным классам, и, следовательно,
код способен исправлять пакеты длины L и
менее.
□
1/--страниц
Пожаловаться на содержимое документа