Цикличен код

Циклични кодовеса сред блоковите систематични кодове, в които всяка комбинация е кодирана независимо (под формата на блок) по такъв начин, че информацията k и контролните t символи винаги се намират

обличайте на определени места. Възможността за откриване и коригиране на практически всякакви грешки със сравнително малък излишък в сравнение с други кодове, както и простотата на схемното изпълнение на оборудването за кодиране и декодиране, направиха тези кодове широко разпространени. Теорията на цикличните кодове се основава на теория на групите и полиномиална алгебра над полето на Галоа.

Цикличният код е код, в който редът на разпределение на кодовите комбинации се извършва по такъв начин, че при преминаване от всяка комбинация към съседна, разстоянието на кода на Хеминг остава постоянно всеки път.

Цикличните кодове са цяло семейство кодове за коригиране на грешки, включително кодовете на Хеминг като една от разновидностите, но като цяло осигуряват по-голяма гъвкавост по отношение на възможността за внедряване на кодове с необходимата способност за откриване и коригиране на грешки, които възникват при предаване на кодови комбинации по комуникационен канал. Цикличният код се отнася до систематични блокови (n, k) кодове, в които първите k бита са комбинация от първичния код, а следващите (n × k) бита са контролни битове.

Конструкцията на циклични кодове се основава на операцията за разделяне на предадената кодова дума на генериращ нередуцируем полином от степен r. Остатъкът от деленето се използва при формирането на контролни битове. В този случай операцията за разделяне се предшества от операция за умножение, която измества k-битовата информационна кодова комбинация наляво с r бита.

Полином (полином), който може да бъде представен като произведение на полиноми от по-ниски степени, се нарича редуцируем (в дадено поле), в противен случай той е неприводим. Нередуцируемите полиноми играят роля, подобна на простите числа в теорията на числата. Нередуцируемите полиноми P(X) могат да бъдат записани като десетични или двоични числа или като алгебричен полином.

Процес на циклично кодиране

Цикличното кодиране се основава на използването на нередуцируем полином P(X), който по отношение на цикличните кодове се нарича генериращ, генериращ или генериращ полином (полином).

Като информационни символи k за конструиране на циклични кодове се вземат комбинации от двоичен код за всички комбинации. В общия случай, ако дадена кодова комбинация Q(x) се умножи по генериращ полином P(x), получаваме цикличен код, който има определени коригиращи свойства в зависимост от избора на P(x). В този код обаче контролните символи m ще бъдат разположени на голямо разнообразие от места в кодовата дума. Такъв код не е систематичен, което затруднява внедряването му в схеми. Ситуацията може да бъде значително опростена, ако контролните знаци се присвоят в края, тоест след информационните знаци. За тази цел е препоръчително да използвате следния метод:

Умножете кодовата дума G(x), която трябва да бъде кодирана с монома X m, имащ същата степен като полинома P(x);

Разделяме произведението G(x)X m на генериращия полином P(x m):

където Q(x) е частното при деление; R(x) - остатък.

Умножавайки израз (2.1) по Р(х) и пренасяйки R(x) в другата част на равенството без обръщане на знака, получаваме:

Така, съгласно равенство (2.2), цикличният код, тоест кодираното съобщение F(x), може да се формира по два начина:

Умножение на една кодова комбинация от двоичен код за всички комбинации с генериращ полином P(x);

Чрез умножаване на дадената кодова дума G(x) по един полином X m със същата степен като генериращия полином P(x), с добавяне на остатъка R(x), получен след разделянето на произведението G(x)X m на генериращият полином P( X).

Кодиране на съобщения

Изисква се да се кодира кодова дума 1100, която съответства на G(x)=x 3 +x 2 с P(x)=x 3 +x+1.

Умножаваме G (x) по X m, което има трета степен, получаваме:

Разделяйки произведението G(x)X m на генериращия полином P(x m), съгласно (2.1) получаваме:

или в двоичен еквивалент:

Така в резултат на това получаваме частно Q(x) със същата степен като G(x):

Q(x)=x 3 +x 2 +x>1110

и останалото:

В резултат на това комбинацията от двоичен код, кодирана от цикличния код, съгласно (2.2), ще приеме формата:

F(x)=1110 1011=1100010

Тъй като всяка разрешена кодова комбинация от цикличен код представлява всички възможни суми на генериращия полином G(x), те трябва да се делят без остатък на P(x). Следователно проверката на коректността на получената кодова комбинация се свежда до идентифициране на остатъка при разделянето му на генериращ полином.

Получаването на остатъка показва наличието на грешка. Остатъкът от деленето в цикличните кодове играе ролята на синдром.

Например предадената кодова комбинация F(x)=1100010, конструирана с помощта на генериращия полином P(x)=1011. Под въздействието на смущения кодовата комбинация се трансформира в комбинация F "(x) = 1000010

Разделяме получената комбинация на генериращия полином

Наличието на остатъка R(x)=001 показва грешка. Той обаче не посочва директно местоположението на грешката в комбинацията. За да се определи грешката, има няколко метода, базирани на анализа на синдрома.

Нека определим местоположението на грешката, за това разделяме единицата с произволен брой нули на P(x)=1011.

Възникна грешка в номер на елемент:

Брой остатъци -2>4-2=2

Тоест грешката е във втория елемент.

Цикличните кодове са наречени така, защото в тях някои или всички комбинации от кода могат да бъдат получени чрез циклично преместване на една или повече комбинации от кода. Цикличното преместване се извършва отдясно наляво, като всеки път най-левият знак се прехвърля в края на комбинацията. Практически всички циклични кодове принадлежат към систематичните кодове, в които контролните и информационните битове са разположени на строго определени места. Освен това кодовете са сред блоковите кодове. Всеки блок (една буква е специален случай на блок) се кодира независимо.

Идеята за конструиране на циклични кодове се основава на използването на нередуцируеми полиноми в областта на двоичните числа. нередуцируемсе наричат ​​полиноми, които не могат да бъдат представени като произведение на полиноми от по-ниски степени с коефициенти от същото поле, както простите числа не могат да бъдат представени като произведение на други числа. С други думи, нередуцируемите полиноми се делят без остатък само на себе си или на единица.

Нередуцируемите полиноми в теорията на цикличните кодове играят ролята на генериращи полиноми. Ако дадената кодова комбинация се умножи по избрания нередуцируем полином, тогава получаваме цикличен код, чиито коригиращи способности се определят от нередуцируемия полином.

Да предположим, че искате да кодирате една от комбинациите от четирицифрен двоичен код. Нека приемем също, че тази комбинация G(x) = x 3 + x 2 + 1® 1011. Без да обосноваваме избора си, вземаме от таблицата на нередуцируемите полиноми като генериращ полином P(x) = x 3 + x + 1® 1011. След това умножете G(x)в моном от същата степен като генериращия полином. От умножаване на полином по моном от степен нстепента на всеки член на полинома ще се увеличи с н, което е еквивалентно на присвояване ннули от младшите цифри на полинома. Тъй като степента на избрания нередуцируем полином е равна на три, първоначалната информационна комбинация се умножава по моном от три степени

G(x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.

Това се прави така, че по-късно на мястото на тези нули да е възможно да се запишат коригиращи битове.

Стойността на коригиращите цифри се намира от резултатите от деленето G(x) x nНа P(x):

x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1

x6 +0+x4 +x3

x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2

x4 + x3 +x2 +0

x 4 + 0 + x 2 + x

x 3 +0+x+0

x 3 +0+x+1

По този начин,

или в общ изглед

Където Q(x)¾ коефициент и R(x)¾ остатък от делението G(x)×xnНа P(x).

Тъй като в двоичната аритметика 1 Å 1 = 0 и следователно -1 = 1, при добавяне на двоични числа е възможно да се прехвърлят термини от една част в друга без промяна на знака (ако е удобно), следователно равенството на формата a Å b = 0 може да се запише и като a = b, И как a - b = 0. И трите равенства в този случай означават, че или аИ bса 0, или аИ bса равни на 1, т.е. имат същия паритет.

Така изразът (5.1) може да бъде записан като

F(x)=Q(x) P(x)= G(x) x n +R(x),

което в случая с нашия пример ще даде

F(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)х 3 + 1,

F(x)= 1111 1011 = 1101000 + 001 = 1101001.

Полиномът 1101001 е желаната комбинация, където 1101- информационна части 001 са контролни знаци. Обърнете внимание, че бихме получили желаната комбинация както в резултат на умножаване на една от комбинациите на пълния четирицифрен двоичен код (в този случай 1111) с генериращ полином, така и чрез умножаване на дадена комбинация по моном със същото степен като избраният генериращ полином (в нашия случай комбинацията 1101000) е получен по този начин, последвано от добавяне към получения продукт на остатъка от деленето на този продукт на генериращия полином (в нашия пример остатъкът има формуляр 001).

И тук свойствата на генериращия полином играят решаваща роля P(x). Методът за конструиране на цикличен код е такъв, че генераторният полином участва във формирането на всяка кодова комбинация, така че всеки полином на цикличния код се разделя от генератора без остатък. Но само онези полиноми, които принадлежат на даден код, т.е. генериращият полином ви позволява да избирате позволени комбинации от всички възможни. Ако при разделянето на цикличния код на генериращия полином се получи остатък, тогава или е възникнала грешка в кода, или това е комбинация от друг код (незаконна комбинация). По остатъка и се открива наличието на забранена комбинация, т.е. открива се грешка. Остатъците от разделянето на полиноми са идентификатори на грешки в цикличните кодове.

От друга страна, остатъците от разделяне на единица с нули на генериращ полином се използват за конструиране на циклични кодове.

Когато разделяте единица с нули на генериращ полином, трябва да се помни, че дължината на остатъка не трябва да бъде по-малка от броя на контролните битове, следователно, в случай на недостиг на битове в остатъка, необходимият брой нули се приписват на остатъка вдясно.

01100 11111+

като се започне от осми, остатъците ще се повторят.

Остатъците от разделянето се използват за конструиране на генериращи матрици, които поради своята видимост и удобство при получаване на производни комбинации се използват широко за конструиране на циклични кодове. Конструкцията на генерираща матрица се свежда до съставянето на единична транспонирана и допълнителна матрица, чиито елементи са остатъците от разделяне на единица с нули на генериращ полином P(x). Спомнете си, че единичната транспонирана матрица е квадратна матрица, всички елементи на която са нули, с изключение на елементите, разположени диагонално отдясно наляво отгоре надолу (в нетранспонирана матрица диагоналът с идентични елементи се намира от отляво надясно, отгоре надолу). Елементите на допълнителната матрица се присвояват отдясно на идентично транспонираната матрица. Само тези остатъци, теглото на които W³d0- 1, където d0- минимално кодово разстояние. Дължината на остатъците трябва да бъде поне броя на контролните битове, а броят на остатъците трябва да бъде равен на броя на информационните битове.

Редовете на генериращата матрица са първите комбинации програмен код. Останалите кодови комбинации се получават в резултат на сумиране по модул 2 на всички възможни комбинации от редове на генериращата матрица.

Пример.

Конструирайте пълна генерираща матрица на цикличен код, който открива всички единични и двойни грешки при предаване на 10-битови двоични комбинации.

Решение.

Според таблица 5.12 изберете най-близката стойност k ³ 10.

Таблица 5.12 - Връзки между информационни и контролни символи за код с дължина до 16 бита

н	к	ρ	н	к	ρ

Според таблицата тази стойност ще бъде k = 11, докато r= 4, А

n= 15. Избираме и генериращ полином x 4 + x 3 +1.

Ние изграждаме пълната генераторна матрица от единично транспонираната матрица в канонична форма и допълнителна матрица, съответстваща на контролните цифри.

Транспонирана матрица за k = 11 изглежда така:

Допълнителна матрица може да бъде конструирана чрез остатъците от разделянето на комбинацията под формата на единица с нули (последния ред на идентично транспонираната матрица) на избрания генериращ полином.

Пълната генерираща матрица ще изглежда така:

Методът за конструиране на генериращи матрици, описан по-горе, не е единственият. Генериращата матрица може да бъде конструирана в резултат на директно умножение на елементите на единичната матрица с генериращия полином. Това често е по-удобно от намирането на остатъка от деление. Получените кодове не се различават по никакъв начин от кодовете, конструирани от генериращи матрици, в които допълнителната матрица се състои от остатъците от деление на единица с нули на генериращ полином.

Генериращата матрица може също да бъде конструирана чрез циклично преместване на комбинацията, получена чрез умножаване на реда на матрицата за идентичност на ранга ккъм генериращ полином.

Грешките в цикличните кодове се откриват с помощта на остатъците от разделянето на получената комбинация на генериращия полином. Остатъците от разделянето са идентификатори на грешки, но не показват директно местоположението на грешката в цикличния код.

Идеята за коригиране на грешки се основава на факта, че грешна комбинация след определен брой циклични смени се „настройва“ към остатъка по такъв начин, че заедно с остатъка дава коригирана кодова комбинация. Остатъкът в този случай не е нищо повече от разликата между изкривените и правилните символи, единиците в остатъка са точно на местата на изкривените битове в комбинацията, коригирана с циклични смени. Изкривената комбинация се коригира, докато броят на единиците в остатъка стане равен на броя на грешките в кода. В този случай, естествено, броят на единиците може да бъде или равен на броя на грешките с,коригирани от този код (кодът коригира 3 грешки и 3 грешки в изкривена комбинация) или по-малко с(кода коригира 3 грешки, а в получената комбинация 1 грешка).

Мястото на грешката в кодовата комбинация няма значение. Ако k³(n/2), след това определена сумасмени, всички грешки ще бъдат в зоната на „единичното“ действие на генериращия полином, т.е. достатъчно е да се получи един остатък, чието тегло W£s, и това вече ще бъде достатъчно, за да коригира изкривената комбинация.

Процесът на коригиране на грешки е разгледан подробно по-долу, като се използват примери за конструиране на специфични кодове.

Цикличните кодове се характеризират с това, че по време на цикличната пермутация на всички символи от кодовата комбинация на даден код се образува друга кодова комбинация от същия код.

Циклична кодова комбинация;

Също така комбинация от цикличен код.

При разглеждане на циклични кодове двоични числаса представени като полином, чиято степен ( П - 1), П- дължината на кодовата комбинация.

Например комбинацията 1001111 ( n= 7) ще бъдат представени от полином

С това представяне операциите върху кодови комбинации се свеждат до операции върху полиноми. Тези операции се извършват в съответствие с обикновената алгебра, с изключение на това, че редуцирането на подобни членове се извършва по модул 2.

Откриването на грешки с помощта на цикличен код се осигурява чрез избиране като разрешени комбинации на тези, които са разделени без остатък от някакъв предварително избран полином Ж(х). Ако получената комбинация съдържа изкривени знаци, тогава разделяне на полином Ж(х) се извършва с остатъка. Това генерира сигнал, показващ грешка. Полином G(х)се нарича генериране.

Конструирането на комбинации от цикличен код е възможно чрез умножаване на оригиналната комбинация А(х) към генериращия полином Ж(х) с намаляване на подобни членове по модул 2:

• ако най-високата мощност на продукта не надвишава ( П - 1), тогава полученият полином ще представлява кодовата комбинация на цикличния код;
• ако най-голямата мощност на продукта е по-голяма или равна на П, тогава полиномът на произведението се дели на предварително избрания полином на степен Пи резултатът от умножението е остатъкът от делението.

По този начин всички полиноми, представляващи комбинации от цикличен код, ще имат степен по-долу П.

Често като полином, чрез който се извършва разделяне, се взема полином Ж(х)= +1. При такова формиране на кодови комбинации позициите на информационните и контролните символи не могат да бъдат определени предварително.

Голямо предимство на цикличните кодове е лекотата на конструиране на енкодери и декодери, които по своята структура представляват преместващи регистри с обратна връзка.

Броят на битовете на регистъра се избира равен на степента на генериращия полином.

Обратна връзкасе извършва от изхода на регистъра до някои цифри чрез суматори, чийто брой се избира с едно по-малко от броя на ненулевите членове на генериращия полином. На входовете на тези битове на регистъра, които съответстват на ненулеви членове на генериращия полином, се инсталират суматори.

Фигура 17 показва схемата на кодиращия регистър за преобразуване на четирибитова комбинация в седембитова комбинация.

Фигура 17 - Схема на кодиращия регистър

В табл. 4 показва как чрез изместване на първоначалната комбинация 0101 се получава цикличната кодова комбинация 1010011. n= 7, к=4. Комбинация 0101, ключ в позиция 1. През първите четири цикъла регистърът ще бъде попълнен, след което ключът се премества в позиция 2. Обратната връзка е затворена. Под действието на седем цикъла на смяна се осъществява образуването на седембитов цикличен код.

Таблица 4

Свойства на цикличен код:

1) цикличният код открива всички единични грешки, ако генериращият полином съдържа повече от един член. Ако Ж(х)=x+ 1, тогава кодът открива единични грешки и всички нечетни;

2) цикличен код с Ж(х)= (x+ 1)Ж(х) открива всички единични, двойни и тройни грешки;

3) цикличен код с генериращ полином Ж(х) степен r = n - kоткрива всичко групови грешкипродължителност в rгерои.

Контролни въпроси

БЕЛОРУСКИ ДЪРЖАВЕН УНИВЕРСИТЕТ ПО ИНФОРМАТИКА И РАДИОЕЛЕКТРОНИКА

Отдел ВЕИ

резюме по темата:

Циклични кодове. BCH кодове"

МИНСК, 2009 г

Циклични кодове

Цикличният код е линеен блоков (n,k)-код, който се характеризира със свойството цикличност, т.е. преместването наляво с една стъпка от всяка разрешена кодова дума също дава позволеното кодова дума, принадлежащи към един и същ код и за които наборът от кодови думи е представен от набор от полиноми от степен (n-1) и по-малка, делим на някакъв полином g(x) от степен r = n-k, който е фактор на биномът x n +1.

Полиномът g(x) се нарича генериращ.

Както следва от дефиницията, кодовите думи в цикличния код са представени като полиноми

където n е дължината на кода; - коефициенти от полето GF(q).

Ако кодът е изграден върху полето GF(2), тогава коефициентите приемат стойности 0 или 1 и кодът се нарича двоичен.
Пример.Ако кодовата дума на цикличния код

след това съответния полином

Например, ако кодът е построен върху полето GF(q)=GF(2 3), което е разширение на GF(2) по модула на нередуцируем полином f(z)=z 3 +z+1, и елементите на това поле имат формата, представена в таблица 1,

след това коефициентите

вземат стойностите на елементите на това поле и следователно самите те се показват като полиноми следния вид
където m е степента на полинома, с който се получава разширението на полето GF(2); a i - коефициенти, които приемат стойността на елементите на GF(2), т.е. 0 и 1. Такъв код се нарича q-ти.

Дължината на цикличен код се нарича примитивен и самият код се нарича примитивен, ако неговата дължина е n=q m -1 върху GF(q).

Ако дължината на кода е по-малка от дължината на примитивния код, тогава кодът се нарича съкратен или непримитивен.

Както следва от дефиницията, общо свойство на кодовите думи на цикличен код е тяхната делимост без остатък от някакъв полином g(x), наречен генератор.

Резултатът от разделянето на бинома x n +1 на полинома g(x) е тестовият полином h(x).

При декодиране на циклични кодове се използват полиномът на грешката e(x) и синдромният полином S(x).

Полиномът на грешката със степен не по-висока от (n-1) се определя от израза

където са полиноми, представляващи съответно получените (по грешка) и предадените кодови думи.

Ненулевите коефициенти в e(x) заемат позиции, които съответстват на грешки.

Пример.

Синдромният полином, използван при декодирането на цикличния код, се дефинира като остатък от разделянето на получената кодова дума на генераторния полином, т.е.

или

Следователно полиномът на синдрома зависи пряко от полинома на грешката e(x).Тази разпоредба се използва при изграждането на таблицата на синдрома, използвана в процеса на декодиране. Тази таблица съдържа списък с полиноми за грешки и списък със съответните синдроми, определени от израза

(виж таблица 2).

В процеса на декодиране синдромът се изчислява от получената кодова дума, след което в таблицата се намира съответният полином e(x), чието сумиране с получената кодова дума дава коригираната кодова дума, т.е.

Изброените полиноми могат да се събират, умножават и делят с помощта на известните правила на алгебрата, но с намален резултат по mod 2 и след това по mod x n +1, ако степента на резултата надвишава степента (n-1).

Да приемем, че дължината на кода е n=7, тогава даваме резултата mod x 7 +1.

При конструиране и декодиране на циклични кодове, в резултат на деление на полиноми, обикновено е необходимо да има не частно, а остатък от деленето.
Затова се препоръчва по-прост метод на разделяне, като се използват не полиноми, а само неговите коефициенти (вариант 2 в примера).

Пример.

Матрично присвояване на кодове

Цикличният код може да бъде даден чрез генериране и проверка на матрици. За да ги конструирате, е достатъчно да знаете генератора g(x) и тестовите h(x) полиноми. За несистематичен цикличен код матриците се конструират чрез циклично изместване на генериращите и проверяващите полиноми, т.е. като ги умножите по x

И

При конструирането на матрицата H (n,k) водещият коефициент на полинома h(x) се намира отдясно.

Пример.За цикличен (7,4) код с генериращ полином g(x)=x 3 +x+1, матриците G (n,k) и H (n,k) имат формата:

Където

За систематичен цикличен код матрицата G (n,k) се определя от израза

където I k е матрицата на идентичност; R k,r - правоъгълна матрица. Редовете на матрицата R k,r се определят от изразите или където a i (x) е стойността на i-тия ред на матрицата I k ; i - номер на ред на матрицата R k,r .

Пример.Матрицата G (n,k) за (7,4)-кода на базата на генериращия полином g(x)=x 3 +x+1 се конструира в следната последователност

или

R 4.3 се определя с помощта на

защото

По подобен начин се определя

Цикличният код е линеен код, който е краен набор, затворен по отношение на операцията на циклично изместване на кодовите вектори, които го формират. Нека се даде н-дименсионален вектор v = а 0 а 1 …a n-1 с координати от полето дестинация Е. Неговото циклично изместване се нарича вектор v"= а н-1 от 0 до 1 ... a n -2 .

Обмисли н-мерно аритметично пространство над поле на Галоа GF(2). Всеки вектор а 0 а 1 …a n-1 от GF(2) може да се асоциира полином едно към едно а 0 +а 1 х+…+a n -1 x n-1 с коефициенти от GF(2). Сумата от два вектора а 0 а 1 …a n-1 и b 0 b 1 …b n-1 съответства на сумата от съответстващите им полиноми, на произведението на елементите на полето по вектора - произведението на полинома, съответстващ на този вектор по елемента.

Помислете за някакъв полином ж(х) от описаното линейно пространство. Наборът от всички полиноми от това подпространство, които се делят без остатък на ж(х) образува линейно подпространство. Линейно подпространство дефинира някакъв линеен код.

Линеен код, образуван от клас полиноми ° С(ж(х)), кратни на някакъв полином ж(х), наречен генериращ полином, се нарича полином.

Нека покажем как са свързани полиномните кодове ° С(ж(х)) и циклични кодове. Позволявам а = а 0 …a n-1 е някаква кодова дума и съответният кодов полином а(х) = а 0 +...+a n -1 x n-1 . циклично изместване а" съответства на кодовия полином а"(х) = a n -1 +а 0 х+…+a n -2 х n -1 , което може да бъде изразено по отношение на оригинала:

Тъй като полиномният код трябва да се дели на ж(х), тогава, за да бъде цикличен, полиномът а"(х) трябва да се дели на ж(х). От това съображение можем да формулираме следната теорема. Един полиномен код е цикличен тогава и само ако полиномът ж(х) е делител на многочлена x n-1. В този случай полиномът ж(х) се нарича генериращ полином на цикличен код.

В теорията на кодирането се доказва следната теорема: ако полином ж(х) има диплома н–ки е делител x n-1 тогава ° С(ж(х)) е линеен цикличен ( н, к)-код.

Полином x n-1 факторизиране x n–1 = (х–1)(x n -1 +x n-1 +...+1). Следователно съществуват циклични кодове за всеки н. Брой циклични н-битови кодове е равен на броя на делителите на полинома x n-1. За конструиране на циклични кодове са разработени таблици за разлагане на полиноми x n-1 за нередуцируеми полиноми, тоест за тези, които се делят само на 1 и себе си.

Помислете, например, какви кодове могат да бъдат построени въз основа на полинома х 7–1 над полето GF(2). Разлагането на полином на несводими множители има формата

Тъй като е възможно да се формират шест делителя на полинома х 7–1, чрез комбиниране на нередуцируеми делители, има шест двоични циклични кода. ( н, к)-кодът се определя първо от стойността н, и второ, стойността к = н – с, се степента на полинома на делителя x n-1 дефиниране на кода. Следват делителите на полинома и съответните им стойности к:

х – 1, с=1, к=6;

х 3 +x 2 +1, с=3, к=4;

х 3 +x+1, с=3, к=4;

(х–1)(х 3 +x 2 +1)=х 4+x 2+x+1, с=4, к=3;

(х–1)(х 3 +x+1)=х 4+x3+x2+1, с=4, к=3;

(х 3 +x 2 +1)(х 3 +x+1)=х 6 +х 5 +х 4 +х 3 +х 2 +х, с=6, к=1.

(7, 6)-кодът има само един символ за проверка, а (7, 1)-кодът има само един информационен символ. Те са съответно код за проверка на четността и код за повторение.

Подобно на обикновения линеен код, цикличният код може да бъде даден от генерираща матрица. Следователно задачата е да се намери такава матрица, тоест да се намери клинейно независими кодови комбинации, които го формират. За това използваме свойството на затваряне на цикличен код по отношение на операцията на циклично изместване. Имайте предвид, че цикличното изместване надясно с една цифра е еквивалентно на умножаване на полинома ж(х) На х. Тогава генериращата матрица може да бъде конструирана чрез вземане като редове на генериращия полином и кнеговите циклични смени:

Нека сега разгледаме как, използвайки генериращия полином ж(х) = 1+х+х 3 се кодира с (7, 4)-код. Вземете например 4-битова дума (0101), която съответства на полинома f(х) = х + х 3 . Умножение на тези два полинома