Пловдивски

43

Информационната скорост на кода C е величината 0<R<1, R=
𝒌
𝒏
.
Означението е (n,k) код.
Пример:
Нека е даден линейният код C={000,011,101,110}, за който n=3, |C|=4.
Оттук следва, че 𝑅 =
log
2
|𝐶|
𝑛
=
2 3
Кодът C е линеен


x,y є C

x

y є C.
Този код не може да коригира грешки, понеже при възникване на единична грешка приетата двоична дума се различава в една позиция с повече от една валидна кодова дума.
𝑐̂ = (111) – сгрешена кодова комбинация

𝑑
0
(𝑐̂, 𝐶)={011,101,110}, което не може да определи точната вярна комбинация.
Пример:
Нека е даден линейният код C={000,111}, за който n=3, |C|=2. Оттук следва, че 𝑅 =
log
2
|𝐶|
𝑛
=
1 3
Този код е пример за т.нар. код с трикратно повторение, при който е възможно коригирането на единична грешка. c=(000) – предадена кодова комбинация,
𝑐̂ = (001) – сгрешена кодова комбинация при приемане

𝑑
0
(𝑐̂, 𝐶)={000}, което означава коригиране до c=(000).
За кодиране на линеен код се използва образуваща матрица – G
k,n
. За декодирането е необходима контролна матрица – H
r,n
. Образуващата матрица в каноничен вид се записва по следния начин:
𝐺
𝑘,𝑛
= ‖𝐸
𝑘
|𝐷
𝑘,𝑟
‖ = ‖
1 0
⋯ 0
𝑑
11
𝑑
12
⋯
𝑑
1𝑟
0 1
⋯ 0
𝑑
21
𝑑
22
⋯
𝑑
2𝑟
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0 0
⋯ 1 𝑑
𝑘1
𝑑
𝑘2
⋯ 𝑑
𝑘𝑟
‖, където E
k е единичната матрица с размерност k x k, а D
k,r е допълнителна матрица, която може да се получи по произволен начин, като се спазват правилата:

всеки ред трябва да съдържа поне d
0
-1 единици;

44

Хеминговото разстояние между всеки два нейни реда трябва да е поне d
0
-2.
Кодираният вектор c=a.G
k,n
, където а е вектора на съобщението.
Контролната матрица може да се получи от допълнителната матрица
D
k,r и единичната матрица E
r с размерност r x r по следния начин:
𝐻
𝑟,𝑛
= ‖𝐷
𝑘,𝑟
𝑇
|𝐸
𝑟
‖ = ‖
𝑑
11
𝑑
21
⋯ 𝑑
𝑘1 1 0 ⋯ 0
𝑑
12
𝑑
22
⋯ 𝑑
𝑘2 0 1 ⋯ 0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
𝑑
1𝑟
𝑑
2𝑟
⋯
𝑑
𝑘𝑟
0 0 ⋯ 1
‖
Основният метод за декодиране на линейни блокови кодове е свързан с изчисляването на синдрома на приетия вектор: 𝑠 = 𝑐̂. 𝐻
𝑇
. Ако полученият синдром е нулев т.е s=(000) то двоичната дума е приета правилно или е възникнала неоткриваема грешка. В противен случай, на всеки ненулев синдром еднозначно е съпоставен вектор на грешката, който се използва за нейната корекция. Осигуряване на такава възможност зависи от броя на контролните елементи. Например, за коригиране на еднократни грешки броят на синдромите трябва да бъде n+1 (n-за грешки във всяка позиция и един за вярно предаване). Тогава броят на контролните битове трябва да бъде r

log
2
(n+1)

2
r

(n+1), r=n-k

2
𝑘
≤
2
𝑛
𝑛+1
. Това неравенство ни дава възможност при зададен брой k на информационните битове в кодовата комбинация да подберем нужната й дължина n.
Следващият пример ще представи този подход на кодиране и декодиране.
Пример:
1. Да се генерира линеен код, съдържащ във всяка своя комбинация 5 информационни бита и коригиращ еднократна грешка.
От условието k=5, а
𝑑
0
−1 2
= 1 (условие за коригиране на еднократна грешка - t=1)

d
0
=3. За осигуряването на достатъчно синдроми трябва да е изпълнено условието r

log
2
(n+1)

2
r

(n+1), r=n-k

2
𝑘
≤
2
𝑛
𝑛+1
. Понеже n>k то за целта k приема стойност 5, а n се замества последователно със стойности, започващи от 6, докато се удовлетвори неравенството. При n=9 условието е изпълнено, което означава, че кодът е (9,5), a r=9-5=4.

45
Според дефинираните по-горе правила за образуващата матрица G
5,9
придобива следния вид:
𝐺
5,9
= ‖𝐸
5
|𝐷
5,4
‖ = ‖
‖
1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1
‖
‖, където условията за D
5,4
са:

всеки ред съдържа поне d
0
-1=3-1=2 единици;

Хеминговото разстояние между всеки два нейни реда е поне d
0
-2=3-
2=1.
2. Да се кодира информационната поредица 11011с новополучения код (9,5) от предходния пример. a(a
1
a
2
a
3
a
4
a
5
)=(11011), c(c
1
c
2
c
3
c
4
c
5
c
6
c
7
c
8
c
9
)=a.G
5,9
= (11011).‖
‖
1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1
‖
‖=
=(110111101), където c i
=a
1
.g
1,i

a
2
.g
2,i

a
3
.g
3,i

a
4
.g
4,i

a
5
.g
5,i

кодираният вектор е c=(110111101).
3. Да се приеме двоичната последователност от т.2.
За целта образуваме контролната матрица H
4,9
, която придобива следния вид:
𝐻
4,9
= ‖𝐷
5,4
𝑇
|𝐸
4
‖ = ‖
1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1
‖
Синдромът получаваме от формулата:

46 s=H
4,9
.c
T
=
‖
1 1 1 1 0 1 0 0 0 1
1 1 0 1 0 1 0 0 1
1 0 1 1 0 0 1 0 1
0 1 1 1 0 0 0 1
‖ .
‖
‖
‖
1 1
0 1
1 1
1 0
1
‖
‖
‖
= ‖
0 0
0 0
‖

синдромът е нулев, което означава, че комбинацията е приета правилно.
4. Да се допусне грешка в третия бит (отляво-надясно) т.е. приетият вектор да е 𝑐̂=(111111101). s=H
4,9
𝑐̂
T
=
‖
1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1
‖ .
‖
‖
‖
1 1
1 1
1 1
1 0
1
‖
‖
‖
= ‖
1 1
0 1
‖

синдромът не е нулев.
Съпоставяме го със стълбовете на контролната матрица H
4,9
за намиране на съвпадение. В този случай полученият синдром съвпада с третия стълб на матрицата, което означава, че трябва да се инвертира третият бит на 𝑐̂. Новополученият вектор 𝑐̂
’
=(110111101) е вярната последователност.

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

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