Задаване на линеен код
Линейните кодове се задават по два начина.
Пораждаща матрица
Чрез пораждаща матрица: G, чиито редове образуват базис на С . Тъй като С има различен базиси, то един и същ код има различни пораждащи матрици: Например:
|1 0 0 1 1| |1 0 0 1 1| G1 = |0 1 0 1 0|, G2 = |1 1 0 0 1| |0 0 1 0 1| |1 1 1 0 0|
Пораждащ един и същ (5,3,2) код, защото G1 u G2 са еквивалентни и векторите от кода са: (00000), (10011), (01010), (00101), (11001), (10110), (01111), (11100) Kато при кода на Хеминг се вижда, че минималното разстояние на линеен код е теглото на най-леката ненулева дума. За дадения пример минималното тегло на ненулевите думи е 2, т.е. d[C] = 2 Ако r1,r2,rk са n-мерните вектори редове на пораждащата матрица u f = [a1,a2,.,ak] е вектор от информационни символи, то неговото представяне в базиса r1, r2,rk на кода е: F=a1r1+a2,r2 ++akrk Което е процентът на кодиране.
Проверочна матрица
Ако С е (n, k,d) код, то С1 е (n, n k, d ) код и може да се зададе с пораждаща матрица Н = ((n-k)xn), редовете на която образуват базис в С1. Тъй като (С1)1 = С, то xC Hx на степен t = 0. H се нарича проверочна матрица за С. Обикновено Н се задава във вид Н = |A|En-k|| , където En-k е единичната матрица от ред n-k. Тогава кодовите вектори са х=(х1,..,хk, xk+1,.,xn), където първите к символа са информационни, а оставащите n-k са проверочни. Ако H = |aij| , то проверочните символи се определят от проверочните съотношения:
xk+1 =nj=1aijxj,i=1,.n-k
И кодирането става както при кода на Хеминг, който беше дефиниран с проверочна матрица. Ако един линеен код е зададен по този начин казваме, че той е систематичен. Пример:
- Кодът с повторение има проверочна матрица
1 1 0 0 Н = 1 0 1 0 1 0 0 1
Лесно се вижда, че един вектор (а1, а2,an) е от кода тогава и само тогава, когато а1 = а2= = аn и единствените вектори с това свойство са (0,0,,0) и (1, 1,,1). Кодът с повторение е (n,1,n) код.
- Код с проверка по четност има проверочна матрица
H = 111111| Вектор (a1, a2, an) е от кода тогава и само тогава, когато a1+a2++an=0, т.е кодовите думи са двоичните п - вектори с четно тегло.
Ако линейният код С има проверочна матрица Н = |А| En-k||, то G = |Ek|A на степен t|| A е пораждаща се С.
Доказателство: Ще докажем, че HG на степен t=0(тук 0 е нулева матрица), т.е. векторите редове на G са ортогонални на тези от Н: i-mu ред на G: x = [0,0,1,0,0, a1i,a2i,a[n-k]i]
i-mu ред на H: y = [aj1,.,aji,ajk,00,1,0,0,]
Вижда се, че xy = aij+aji=0. Тогава всеки ред на G е от кода С, но рангът на G e kG е пораждаща матрица на код С
Пример. В пример 5.10 беше дадена проверочната матрица на (7,4,3)- кода на Хеминг. Пораждащата матрица е:
1 0 0 0 1 1 1 0 1 0 0 1 1 0 G = 0 0 1 0 1 0 1 0 0 0 1 0 1 1
Нека С е линеен код с проверочна матрица Н. На всяка кодова дума с тегло t съответства линейна зависимост на t стълба от Н и обратно, на всяка линейна зависимост на t стълба от Н съответства кодова дума с тегло t от С. От теоремата следва, че линеен код С е проверочна матрица Н имаме d(C)=d тогава и само тогава, когато всеки d-1 стълба на Н са линейно независими, но съществуват d линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
Вижте още
Източници
- David Poole, Linear Algebra: A Modern Introduction
- A. H. Land and S. Powell, Fortran Codes for Mathematical Programming: Linear, Quadratic and Discrete
- Bernard Kolman and Robert E. Beck, Elementary Linear Programming with Applications, Second Edition (Computer Science & Scientific Computing Series)
- Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sherali, Linear Programming and Network Flows