Рийд-Мюлер код


Категория на документа: Други


Курсова работа
по
Кодиране и защита на информацията

Тема:
Рийд - Мюлер код

1)Въведение
Рийд- Мюлер кодовете са едни от най-старите кодове за коригиране на грешки.
Кодовете за коригиране на грешки са много полезни при изпращане на информация на дълги разстояния, или през канали, където могат да се случат грешки в съобщението. Те са станали по-преобладаващи когато телекомуникацията се е развила за да използва кодове които могат да се самопоправят . Рийд Мюлер кодовете са открити през 1954 г. от Д. E. Мюлер и И.С Рийд. През 1972 г. Рийд - Мюлер кода е бил използван от Маринър 9 за предаване на чернобели
фотографии от Марс . Рийд - Мюлер кодовете са относително лесни за декодиране.

2)Дефиниция и операции
Пространствените вектори, използвани в този документ се състоят от низове с дължина 2m, където m е положително цяло число от номера в F2 = f0, 1г.
Кодовите думи на Рийд - Мюлер кода образуват подпространство на пространството .Такива вектори могат да бъдат манипулирани от три основни операции: събиране, умножение и точков продукт.
За двата вектора x = (x1; x2;....; xn) и y = (y1; y2;....; yn) допълнението се изразява чрез :
x + y = (x1 + y1; x2 + y2; : : : ; xn + yn)
където всяко xi или yi е или 1 или 0 и :
1 + 1 = 0; 0 + 1 = 1; 1 + 0 = 1; 0 + 0 = 0
За пример ако x и y са изразени с x = (10011110) и y = (11100001) , тогава сумата им е :
x + y = (10011110) + (11100001) = (01111111)
допълнението на скаларната величина a € F2 към вектор x се изразявя чрез :
a + x = (a + x1; a + x2;....; a + xn)
Допълнението Ẍ на вектора X е вектор равен на 1+x.За пример :
1 + (000111) = (111000)
Умножението се изразява чрез формулата :
x * y = (x1 _ y1; x2 _ y2;...; xn _ yn);
където всяко xi и yi е или 1 или 0 и :
1 * 1 = 1; 0 * 1 = 0; 1 * 0 = 0; 0 * 0 = 0:
За пример използваме същите вектори от по-горе :
x *y = (10011110) * (11100001) = (10000000)
Умножението на константата a € F2 към вектора X е изразено чрез :
a * x = (a * x1; a * x2;.....; a *xn)
Например 0 * (111001) = (000000). Точковия продукт на х и y е представен чрез :
x . y = x1 * y1 + x2 * y2 + .... + xn * yn:
Използваме за пример векторите отгоре :
x . y = (10011110) .(11100001) = 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 1:
Всичките три операции изискват вектори, имащи същия брой на координатите.Векторите могат да бъдат свързани с булеви полиноми. Булевия полином е линейна комбинация от Булева едночлени с коефициенти в F2.Булевия едночлен p в променливите x1;...; xm, се изразява като :
P=x1r1x2r2......xmrm , където ri € {0,1,2....} и 1≤ i ≤ m
Редуцираната форма p' на p се получава чрез изпълнението на правилата:
xixj=xjxi и xi2=xi
докато факторите са различни . Степента на p е обикновенната степен на p' , която е номер на променливите в p'. Булевия полином е в редуцирана форма, ако всеки едночлен
е в редуцирана форма. Степента на булевия полином q е обикновенaта степен на неговата
редуцирана форма q'
Пример за Булев полином в редуцирана форма с трета степен е:
q = x1 + x2 + x1x2 + x2x3x4

3)Процедура на кодиране
В r реда Рийд-Мюлер кода R(r,m) е комбинация от всички бинарни вектори в обсег n=2m асоциирана с Булевите полиноми p(x1; x2;...; xm) със степен в повечето r . В нулевия ред Рийд-Мюлер кода R(0,m) се състои от бинарни вектори свързващи се с константните полиноми 0 и 1 :
R(0;m) = {0; 1} = Rep(2m):
Следователно R(0;m) е повторение на едно от нулите или едно от тези с дължина 2m.В другата крайност m реда на Рийд-Мюлер кода R(m,m) се състои от бинарни вектори с дължина 2m



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





Яндекс.Метрика
Рийд-Мюлер код 9 out of 10 based on 2 ratings. 2 user reviews.