Пловдивски

47
Нека h=3

n=2
h
-1=2 3
-1=7, k=2
h
-1-h=2 3
-1-3=4

двоичен линеен (7, 4)
-код на Хеминг.
Контролната матрица H
r,n съгласно определението ще бъде:
H
3,7
=
‖
1 1 1 0 1 0 0 1
1 0 1 0 1 0 1
0 1 1 0 0 1
‖
На базата на тази матрица и дефинираните по-горе правила можем да получим образуващата матрица G
k,n
:
G
4,7
=
‖
1 0 0 0 1 1 1 0
1 0 0 1 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 1
‖
4.3.2. Линеен код с една проверка по четност
Обозначава се като (n,n-1)-код (single parity check code). При него към всяка последователност от n-1 информационни бита се добавя един контролен бит, който е равен на сумата им по mod2 т.е.: c
1
=a
1
, c
2
=a
2
, … c n-1
=a n-1
, c n
=a
1

a
2

…

a n-1
Всяка кодова комбинация съдържа винаги четен брой единични елементи. Кодово разстояние е d
0
=2 (едно за информационния бит и едно за контролния бит). Открива комбинация от нечетен брой грешки
(еднократна, трикратна, петкратна и т.н.).
4.4. Циклични (Cyclic Redundancy Check - CRC) кодове
Намират широко приложение в практиката. Притежават следните основни свойства:

ако кодовата комбинация c
1
, c
2
… c n
, принадлежи на цикличен код, то и c n
, c
1
…c n-1
и т.н. също принадлежат на дадения цикличен код.

съществува единствен нормиран полином g(x)∈C от най-ниска степен, на който се делят без остатък всички кодови комбинации, разрешени за даден цикличен код. Забранените комбинации генерират остатък при делението. Всяка кодова комбинация може да се представи като полином, като всеки неин елемент се

48 разглежда като коефициент пред степен на променливата x, съответстваща на мястото на дадения елемент в комбинацията.
Пример:
c=(110111)

c(x)=1.х
5
+1.х
4
+0.x
3
+1.х
2
+1.х
1
+1.х
0
т.е. всеки полином може да се отъждестви с наредената (n+1)-орка (c
0
c
1
…c n
).
Множеството от всички полиноми отговарящи на допустимите кодови комбинации на даден цикличен код образува поле на Галоа - GF(x), в което действията над коефициентите на полиномите се извършват по mod2.
Полиномът g(x) на (n,k) цикличен код C удовлетворява следните условия:
1. g(x)
∈ C e нормиран полином от най-ниска степен;
2. g(x) дели без остатък х n
-1;
3. степента му е равна на броя на контролните елементи r = n-k в кодовата комбинация;
4. осигурява максимален брой остатъци, за корекция на различните грешки;
5. ако g(x) =g
0
+g
1
.x+· ·+g r−1
x r−1
+x r
, то образуващата матрица на този подклас линейни кодове се получава чрез циклично преместване на образуващия полином g(x):
G = ‖
𝑔
0
𝑔
1
⋯ 𝑔
𝑟−1 1
0
⋯ 0 0
𝑔
0
⋯
𝑑
r−2
𝑑
𝑟−1 1
⋯ 0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0 0
⋯
0
𝑔
0
𝑔
0
⋯ 1
‖
Алгоритъм за кодиране на информационна поредица чрез CRC код:

полиномът a(x), съответстващ на информационната поредица, която трябва да се кодира, се умножава с х n-k

полученият полином a(x).х n-k се дели на образуващия полином g(x)
и се намира остатъкът от делението r(x).

полиномът r(x) се прибавя (по mod2) към делимото a(x).х n-k
F(x)=a(x).х n-k

r(x) – задава двоичната последователност за предаване.
Пример:

49 1.
Да се кодира информационната поредица 1011 чрез използване на цикличен (8,4) – код с образуващ полином – g(x)=х
4
+х+1.
Стъпка 1: Образуващият полином се представя като двоична последователност от коефициентите пред степените на x: g(x)=х
4
+х+1

g=(10011).
Стъпка 2: Информационната поредица 1011 се измества наляво с r=n-k=4 нулеви бита: 1011

10110000.
Стъпка 3: Получената двоична последователност се дели на g(x) и се определя остатъкът от делението r(x):
Стъпка 4: Полученият остатък се събира по mod2 с делимото:
Получената последователност 10111110 се предава по канала (фигура
25).

Изтегляне 7.37 Mb.

Сподели с приятели: