Линеен код - Редакционна история

Detelina Staneva: /* Задаване */

2014-03-25T12:29:55Z

Задаване

Detelina Staneva: /* Вижте още */

2014-03-25T12:17:29Z

Вижте още

Detelina Staneva: /* Вижте още */

2012-07-15T11:22:53Z

Вижте още

Detelina Staneva в 10:48, 15 юли 2012

2012-07-15T10:48:26Z

Detelina Staneva в 10:47, 15 юли 2012

2012-07-15T10:47:11Z

Detelina Staneva в 10:37, 15 юли 2012

2012-07-15T10:37:44Z

Detelina Staneva: /* Пораждаща матрица */

2012-07-15T10:36:04Z

Пораждаща матрица

Detelina Staneva: /* Задаване */

2012-07-15T10:35:49Z

Задаване

Detelina Staneva: Нова страница: '''Всяко подпространство С на V на степен n''' се нарича '''линеен код'''. ==Същност== Ако dimC = k , то С с...

2012-07-15T10:34:42Z

Нова страница: '''Всяко подпространство С на V на степен n''' се нарича '''линеен код'''. ==Същност== Ако dimC = k , то С с...

Нова страница

'''Всяко подпространство С на 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
==Задаване==
Линейните кодове се задават по два начина:
===Пораждаща матрица===
Чрез пораждаща матрица: 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 линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
==Вижте още==
==Източници==
==Външни препратки==
[[category:Информатика]]

@@ Ред 5: / Ред 5: @@
 Ще дадем една [[интерпретация]] на линейните кодове, която ги свързва с комбинаторните покрития От векторите на (п, 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
 ==Вижте още==
 *[[Задаване на линеен код]]

@@ Ред 63: / Ред 63: @@
 От теоремата следва, че линеен код С е проверочна матрица Н имаме d(C)=d тогава и само тогава, когато всеки d-1 стълба на Н са линейно независими, но съществуват d линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
 ==Вижте още==
 *[[Двоичен код]]
 *[[Изходен код]]

@@ Ред 63: / Ред 63: @@
 От теоремата следва, че линеен код С е проверочна матрица Н имаме d(C)=d тогава и само тогава, когато всеки d-1 стълба на Н са линейно независими, но съществуват d линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
 ==Вижте още==
-*[[Програмиране]]
+*[[Двоичен код]]
 *[[Изходен код]]
 *[[Машина]]
@@ Ред 71: / Ред 71: @@
 *[[Изкуствен интелект]]
 *[[Програма]]
 ==Източници==
 *David Poole, Linear Algebra: A Modern Introduction

← По-стара версия		Версия от 10:37, 15 юли 2012
Ред 1:		Ред 1:
		+	[[file:dlk.jpg\|right\|thumb\|С е двоичен линеен код с пораждаща матрица]]
	'''Всяко подпространство С на V на степен n''' се нарича '''линеен код'''.		'''Всяко подпространство С на V на степен n''' се нарича '''линеен код'''.
	==Същност==		==Същност==

@@ Ред 3: / Ред 3: @@
 ==Същност==
 Ако 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
 ==Задаване==
 Линейните кодове се задават по два начина:
 ===Пораждаща матрица===
-Чрез пораждаща матрица: G, чиито редове образуват базис на С . Тъй като С има различен базиси, то един и същ код има различни пораждащи матрици: Например:
+Чрез пораждаща [[матрица]]: G, чиито редове образуват базис на С . Тъй като С има различен базиси, то един и същ код има различни пораждащи матрици: Например:
 |1 0 0 1 1| |1 0 0 1 1|
@@ Ред 18: / Ред 18: @@
 (11001), (10110), (01111), (11100)
 Kато при кода на Хеминг се вижда, че минималното разстояние на линеен код е теглото на най-леката ненулева дума. За дадения пример минималното тегло на ненулевите думи е 2, т.е. d[C] = 2
-Ако r1,r2,rk са n-мерните вектори редове на пораждащата матрица u f = [a1,a2,.,ak] е вектор от информационни символи, то неговото представяне в базиса r1, r2,rk на кода е:
+Ако r1,r2,rk са n-мерните [[вектор]]и редове на пораждащата матрица u f = [a1,a2,.,ak] е вектор от информационни символи, то неговото представяне в базиса r1, r2,rk на кода е:
 F=a1r1+a2,r2 ++akrk
 Което е процентът на кодиране.
@@ Ред 24: / Ред 24: @@
 ===Проверочна матрица===
-Ако С е (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| , то проверочните символи се определят от проверочните съотношения:
+Ако С е (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

@@ Ред 62: / Ред 62: @@
 Нека С е линеен код с проверочна матрица Н. На всяка кодова дума с тегло t съответства линейна зависимост на t стълба от Н и обратно, на всяка линейна зависимост на t стълба от Н съответства кодова дума с тегло t от С.
 От теоремата следва, че линеен код С е проверочна матрица Н имаме d(C)=d тогава и само тогава, когато всеки d-1 стълба на Н са линейно независими, но съществуват d линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
 ==Вижте още==
 ==Източници==
 ==Външни препратки==
 [[category:Информатика]]

@@ Ред 10: / Ред 10: @@
 |1 0 0 1 1| |1 0 0 1 1|
-G1 = |0 1 0 1 0|, G2= |1 1 0 0 1|
+G1 = |0 1 0 1 0|, G2 = |1 1 0 0 1|
 |0 0 1 0 1| |1 1 1 0 0|
@@ Ред 16: / Ред 16: @@
 (00000), (10011), (01010), (00101),
 (11001), (10110), (01111), (11100)
-Kато при кода на Хеминг се вижда, че минималното разстояние на линеен код е теглото на най-леката ненулева дума. За дадения пример минималното тегло на ненулевите думи е 2, т.е. d[C]=2
+Kато при кода на Хеминг се вижда, че минималното разстояние на линеен код е теглото на най-леката ненулева дума. За дадения пример минималното тегло на ненулевите думи е 2, т.е. d[C] = 2
-Ако r1,r2,rk са n-мерните вектори редове на пораждащата матрица u f=[a1,a2,.,ak] е вектор от информационни символи, то неговото представяне в базиса r1, r2,rk на кода е:
+Ако r1,r2,rk са n-мерните вектори редове на пораждащата матрица u f = [a1,a2,.,ak] е вектор от информационни символи, то неговото представяне в базиса r1, r2,rk на кода е:
 F=a1r1+a2,r2 ++akrk
 Което е процентът на кодиране.
 ===Проверочна матрица===

@@ Ред 22: / Ред 22: @@
 ===Проверочна матрица===
-Ако С е (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| , то проверочните символи се определят от проверочните съотношения:
+Ако С е (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
@@ Ред 29: / Ред 29: @@
 Пример:
-а/ Кодът с повторение има проверочна матрица
+*Кодът с повторение има проверочна матрица
 1 0 0
@@ Ред 37: / Ред 37: @@
 Лесно се вижда, че един вектор (а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 е пораждаща се С.
+Ако линейният код С има проверочна матрица Н = |А| 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 ред на G: x = [0,0,1,0,0, a1i,a2i,a[n-k]i]
-i-mu ред на H: y =[aj1,.,aji,ajk,00,1,0,0,]
+i-mu ред на H: y = [aj1,.,aji,ajk,00,1,0,0,]
-Вижда се, че xy=aij+aji=0. Тогава всеки ред на G е от кода С, но рангът на G e kG е пораждаща матрица на код С
+Вижда се, че xy = aij+aji=0. Тогава всеки ред на G е от кода С, но рангът на G e kG е пораждаща матрица на код С
 Пример. В пример 5.10 беше дадена проверочната матрица на (7,4,3)- кода на Хеминг. Пораждащата матрица е:
@@ Ред 60: / Ред 60: @@
 Нека С е линеен код с проверочна матрица Н. На всяка кодова дума с тегло t съответства линейна зависимост на t стълба от Н и обратно, на всяка линейна зависимост на t стълба от Н съответства кодова дума с тегло t от С.
 От теоремата следва, че линеен код С е проверочна матрица Н имаме d(C)=d тогава и само тогава, когато всеки d-1 стълба на Н са линейно независими, но съществуват d линейно зависими стълба. Демонстрация на този факт направихме при определяне минималното разстояние на кода Хеминг.
 ==Вижте още==
 ==Източници==
 ==Външни препратки==
 [[category:Информатика]]