Тема Контрол на компютърните системи
Изтегляне 251.5 Kb.
|
Свързани:
avtoreferat, discrete structure, Математически методи за цифрова обработка, 11168, 6656474, 2008-05-05-19-19-Paranoia Doll-seti lab-bl
- Навигация на страницата:
- Построяване на цикличен код
| 2.3.2. Цикличен код
При цикличните кодове част от комбинациите на кода или всички комбинации могат да се получат чрез циклично изместване на една или няколко комбинации на кода. Цикличното изместване се извършва чрез свързване на изхода на старшия бит с входа на нулевия бит. Цикличните кодове са систематични (информационните и контролните разряди са разположени по строго определена система и винаги заемат строго определени места в кодовата комбинация) и равномерни (всички комбинации на кода имат еднаква дължина). Построяване на цикличен код Идеята на построяването на цикличните кодове се основава на използването на неразложими в полето на двоичните числа полиноми (делят се без остатък само сами на себе си и на единица). Те се използват в качеството на образуващи, тъй като ако дадена кодова комбинация се умножи на избран неразложим полином ще се получи цикличен код, чийто контролиращи и коригиращи възможности ще зависят от този полином. Изходното съобщение с дължина т бита се представя като системен полином Р(х) от степен (m-1) спрямо някаква фиктивна променлива х. В зависимост от изискванията към кода (да открива грешки или да открива и отстранява грешките) се определя броя на допълнителните контролни разряди k, които ще се формират. Ако кодът ще открива грешки, трябва да се осигури минимално кодово разстояние (това е броят на разрядите, по които се различават две последователни разрешени кодови комбинации) (r - кратност на грешката), а ако ще открива и коригира грешки: dmin 2r +1. С добавянето на k контролни разряда ще се получи кодово съобщение с дължина п = т + k. Връзката между п и k се дава с неравенството: , (2.3) Броят на контролните разряди k определя степента на образуващият полином G(x). Той се избира от групата на неразложимите полиноми (таблица). За формирането на кодов полином F(x) изходното съобщение Р(х) се измества k разряда наляво, т.е. умножава се с едночлен хk, а на мястото на освободените k бита се записва остатъкът R(x) от делението на P(x).xk c G(x). Така полученият полином F(x) се дели на G(x) без остатък: , (2.3а) където Q(х) е частното от деленето. Тъй като в двоичната аритметика , а следователно 0-1=1, то е възможно при събирането на двоични числа да се пренасят събираеми от една част на равенството в друга без изменение на знака (ако това е нужно), поради което равенства от вида може да се запише като a=b и като a-b=0. И трите равенства в даденият случай означават, че или а и b са равни на 0, или а и b са равни на 1, т.е. имат еднаква четност. На базата на изложеното израз (2.3а) за F(x) може да се запише като: P(x).xk= Q(x).G(x) + R(x) или Q(x).G(x) = P(x).xk + R(x). (2.3б) Полиномът в лявата част на (2.3б) Q(x).G(x) се дели без остатък на G(x) и следователно неговите коефициенти са търсената кодова комбинация. Следователно коефициентите на полинома, който е сума на P(x).xk и остатъка от делението на P(x).xk с G(x), са кодовата комбинация, подлежаща на предаване. Изтегляне 251.5 Kb. Сподели с приятели:
|