Разлика между версии на „Линеен код“

От Администрация и управление
Направо към навигацията Направо към търсенето
 
(Не са показани 4 междинни версии от същия потребител)
Ред 3: Ред 3:
 
==Същност==
 
==Същност==
 
Ако dimC = k , то С се нарича (п.к) код. Ако d (C ) = d, то С се нарича |п.к.d|- код.
 
Ако dimC = k , то С се нарича (п.к) код. Ако d (C ) = d, то С се нарича |п.к.d|- код.
−
Ще дадем една интерпретация на линейните кодове, която ги свързва с комбинаторните покрития От векторите на (п, k, d ) - код образуваме матрица A= a|ij| , в която те са редове. Матрицата А се тълкува като матрица на инцидентност в следния смисъл: j-mu стълб съответства на елемент j S(п), а i-mu ред съответства на подмножество Bi (блок), като jB1 <=> aij =0(т.е. тук нулата е знак на инцидентност). Сега е ясно, че за всеки блок Bi, |Bi| n-d, Блоковете не са равномощни, но чрез произволно допълване с елементи от S[n] можем да ги направим такива. Чрез индукция по k се доказва [23], че всяка [k -1]-орка на S[n] се съдържа в някой блок Bi , т.е. блоковете образуват (n,n-d,k-1) покритие и очевидното следствие е n-d k-1, откъдето се получава неравенството на Сингълтън за разстоянието на линеен ( n,k,d ) код:
+
Ще дадем една [[интерпретация]] на линейните кодове, която ги свързва с комбинаторните покрития От векторите на (п, k, d ) - код образуваме матрица A = a|ij| , в която те са редове. Матрицата А се тълкува като матрица на инцидентност в следния смисъл: j-mu стълб съответства на елемент j S(п), а i-mu ред съответства на [[подмножество]] Bi (блок), като jB1 <=> aij =0(т.е. тук нулата е знак на инцидентност). Сега е ясно, че за всеки блок Bi, |Bi| n-d, Блоковете не са равномощни, но чрез произволно допълване с елементи от S[n] можем да ги направим такива. Чрез индукция по k се доказва [23], че всяка [k -1]-орка на S[n] се съдържа в някой блок Bi , т.е. блоковете образуват (n,n-d,k-1) покритие и очевидното [[следствие]] е n-d k-1, откъдето се получава неравенството на Сингълтън за разстоянието на линеен ( n,k,d ) код:
 
d[C]=d n-k+1
 
d[C]=d n-k+1
−
==Задаване==
+
==Вижте още==
−
Линейните кодове се задават по два начина:
+
*[[Задаване на линеен код]]
−
===Пораждаща матрица===
+
*[[Двоичен код]]
−
Чрез пораждаща матрица: 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
 
==Външни препратки==
 
==Външни препратки==
 +
*[http://techs-mobile.blogspot.com/2010/06/blog-post.html Импулсно-кодова модулация]
 +
*[https://docs.google.com/viewer?a=v&q=cache:g1H_j1w9PCsJ:www.math.bas.bg/vt/mch/WebSchoolApril/Kodirane/15.pdf+&hl=bg&gl=bg&pid=bl&srcid=ADGEESjap-Cs4eMApGIr-ovq3eGeuRZACVDlVQqBSUhGiWUYYfhb4FVV7I8T9cofYjjz_bDscmHQfeMHMfNhwI2PZKmEXWEK0tg2xg108SnAjDzfX07Y58DCBvNuKTNGa3iu192zhqPL&sig=AHIEtbRztJcORfuNJkF4CFW0FvkFMobPkA Циклични кодове]
 +
*[https://docs.google.com/viewer?a=v&q=cache:qaE46B4jM-gJ:www.uni-vt.bg/pages/591/uplft/primeren_test_coding.pdf+&hl=bg&gl=bg&pid=bl&srcid=ADGEEShUSNQ_a8qrf5VjPys34qYX1EUDOxL_P7r9lk8OE1U604yd1hQyhLHRX_HnhbRGs9Z3lI99XhmXs-3qOZOwksxgj6-syhMeKNsrNEzPeoV-8O8XhmD7qFhmEOwFAIkh_ddjsFHe&sig=AHIEtbTGuRkeBAyBG6Wrmlh6d7AI3LZ31Q Шумозащитно кодиране]
 +
*[https://docs.google.com/viewer?a=v&q=cache:V2UUZlJX6vQJ:www.fmi.uni-sofia.bg/algebra/lectures_aageometry/master1_aageom.pdf+&hl=bg&gl=bg&pid=bl&srcid=ADGEEShm08E_ZagX_typj099PWiORyj6Ek85iDGORfbzBdU-vngxiK8VLH47zJnwPOAbNA92-zqJ-OmmElECCyJMtURAbbVkwkK8-U0_gRLEXK4pxcAGvNuRazefZP2erWps9ceNyQJm&sig=AHIEtbRi0Sd52hVoI4etF-O2GsQuDfHX_w Мотивация]
 +
*[http://www.math10.com/f/viewtopic.php?f=35&t=235 Уравненията на Mac Williams]
 
[[category:Информатика]]
 
[[category:Информатика]]

Текуща версия към 15:29, 25 март 2014

С е двоичен линеен код с пораждаща матрица

Всяко подпространство С на V на степен n се нарича линеен код.

Същност

Ако dimC = k , то С се нарича (п.к) код. Ако d (C ) = d, то С се нарича |п.к.d|- код. Ще дадем една интерпретация на линейните кодове, която ги свързва с комбинаторните покрития От векторите на (п, k, d ) - код образуваме матрица A = a|ij| , в която те са редове. Матрицата А се тълкува като матрица на инцидентност в следния смисъл: j-mu стълб съответства на елемент j S(п), а i-mu ред съответства на подмножество Bi (блок), като jB1 <=> aij =0(т.е. тук нулата е знак на инцидентност). Сега е ясно, че за всеки блок Bi, |Bi| n-d, Блоковете не са равномощни, но чрез произволно допълване с елементи от S[n] можем да ги направим такива. Чрез индукция по k се доказва [23], че всяка [k -1]-орка на S[n] се съдържа в някой блок Bi , т.е. блоковете образуват (n,n-d,k-1) покритие и очевидното следствие е n-d k-1, откъдето се получава неравенството на Сингълтън за разстоянието на линеен ( n,k,d ) код: d[C]=d n-k+1

Вижте още

Източници

  • 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

Външни препратки

Взето от „https://wiki.basaga.org/index.php?title=Линеен_код&oldid=13129“.