O código cíclico c mais simples permite detectar erros únicos e erros de multiplicidade ímpar. O polinômio gerador deste código tem a forma Entre os polinômios irredutíveis incluídos na expansão, este polinômio é o polinômio de menor grau. Assim, para qualquer número de bits de informação, é necessário apenas um bit de verificação. O valor do símbolo deste bit garante a uniformidade do número de unidades em qualquer combinação de código permitida. O código de paridade cíclica resultante é capaz de detectar não apenas erros únicos em bits individuais, mas também erros em qualquer número ímpar de bits.

Exemplo. Construa um código cíclico para Como o polinômio gerador é um polinômio de 1º grau, o número de dígitos de verificação Portanto, para construir um código cíclico, construímos uma matriz geradora

Para construir uma matriz adicional, encontramos os restos da divisão da última linha da matriz unitária transposta, preenchida com zeros, pelo polinômio selecionado:

Assim, a matriz adicional C,k tem a forma

Agora construímos a matriz geradora

As linhas desta matriz são as três primeiras combinações de códigos. O resto das combinações permitidas podem ser obtidas somando o módulo dois de todas as combinações possíveis de linhas da matriz. As combinações de código destruídas resultantes são fornecidas na Tabela. 39.

Tabela 39 (ver digitalização)

De interesse bem conhecido é a consideração do seguinte código mais simples formado usando um polinômio irredutível de segundo grau

A forma geral da matriz geradora de um código cíclico formado por um polinômio difere na estrutura de uma matriz adicional com duas colunas.

É fácil verificar que ao dividir por um determinado polinômio gerador os monômios que expressam as strings

matriz identidade (para encontrar uma matriz adicional, três tipos de restos são formados: 11, 01 e 10. Consequentemente, o peso de cada combinação do código resultante será de pelo menos dois. A distância mínima do código entre quaisquer duas combinações também é dois Mas o mais simples também é caracterizado pelos mesmos valores de um código com uma verificação de paridade formada por um binômio de primeiro grau. Porém, a capacidade de correção de ambos os códigos não é a mesma. é possível detectar não apenas quaisquer erros de multiplicidade ímpar, mas também quaisquer erros adjacentes emparelhados, bem como todos os erros separados por um elemento não corrompido.

Um código cíclico é um código linear, que é um conjunto finito que é fechado sob a operação de deslocamento cíclico dos vetores de código que o formam. Deixe ser dado n vetor tridimensional v = a 0 a 1 …um-1 com coordenadas do campo final F. Seu deslocamento cíclico é chamado de vetor v"= um n-1 a 0 a 1… um -2 .

Vamos considerar n espaço aritmético tridimensional sobre um campo de Galois GF(2). Cada vetor a 0 a 1 …um-1 de GF(2) pode-se comparar o polinômio um a um a 0 +a 1 x+…+um -1 x n-1 com probabilidades de GF(2). A soma de dois vetores a 0 a 1 …um-1 e b 0 b 1 …b n-1 é colocado em correspondência com a soma dos polinômios que lhes correspondem, o produto dos elementos do corpo pelo vetor - o produto do polinômio correspondente a este vetor pelo elemento.

Vamos considerar algum polinômio g(x) do espaço linear descrito. O conjunto de todos os polinômios deste subespaço que são divisíveis sem resto por g(x), forma um subespaço linear. Um subespaço linear define algum código linear.

Código linear formado por uma classe de polinômios C(g(x)), múltiplos de algum polinômio g(x), chamado de polinômio gerador, é chamado de polinômio.

Vamos mostrar como os códigos polinomiais estão relacionados C(g(x)) e códigos cíclicos. Deixar a = a 0 …um-1 é alguma palavra de código e o polinômio de código correspondente a(x) = a 0 +...+um -1 x n-1. Mudança cíclica a"corresponde ao polinômio do código a"(x) = um -1 +a 0 x+…+um -2 x n -1 , que pode ser expresso em termos do original:

Como um código polinomial deve ser divisível por g(x), então para que seja cíclico, o polinômio a"(x) deve ser divisível por g(x). A partir desta consideração podemos formular o seguinte teorema. Um código polinomial é cíclico se e somente se o polinômio g(x) é um divisor do polinômio x n-1. Neste caso o polinômio g(x) é chamado de polinômio gerador do código cíclico.

Na teoria da codificação, o seguinte teorema é provado: se um polinômio g(x) tem um diploma n–k e é um divisor x n–1, então C(g(x)) é linear cíclico ( n, k)-código.

Polinomial x n–1 fatorar x n–1 = (x–1)(x n -1 +x n-1+…+1). Portanto, existem códigos cíclicos para qualquer n. Número de cíclicos n-códigos de bits iguais ao número de divisores do polinômio x n-1. Tabelas de expansão polinomial foram desenvolvidas para construir códigos cíclicos x n–1 em polinômios irredutíveis, isto é, naqueles que são divisíveis apenas pela unidade e por si mesmo.

Consideremos, por exemplo, quais códigos podem ser construídos com base no polinômio x 7 –1 em campo GF(2). A expansão do polinômio em fatores irredutíveis tem a forma

Como é possível formar seis divisores de um polinômio x 7–1, combinando divisores irredutíveis, existem seis códigos cíclicos binários. ( n, k)-código é determinado, em primeiro lugar, pelo valor n, e em segundo lugar, o valor k = n – é, é– grau do polinômio divisor x n–1, que define o código. Abaixo estão os divisores polinomiais e seus valores correspondentes k:

x – 1, é=1, k=6;

x 3 +x 2 +1, é=3, k=4;

x 3 +x+1, é=3, k=4;

(x–1)(x 3 +x 2 +1)=x 4 +x 2 +x+1, é=4, k=3;

(x–1)(x 3 +x+1)=x 4 +x 3 +x 2 +1, é=4, k=3;

(x 3 +x 2 +1)(x 3 +x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, é=6, k=1.

O código (7, 6) possui apenas um símbolo de verificação e o código (7, 1) possui apenas um símbolo de informação. São, respectivamente, um código de verificação de paridade e um código de repetição.

Como um código linear regular, um código cíclico pode ser especificado por uma matriz geradora. Portanto, a tarefa é encontrar tal matriz, ou seja, encontrar k combinações de código linearmente independentes que o formam. Para tanto, utilizamos a propriedade do código cíclico ser fechado em relação à operação de deslocamento cíclico. Observe que um deslocamento cíclico de uma casa para a direita é equivalente a multiplicar o polinômio g(x) sobre x. Então a matriz geradora pode ser construída tomando o polinômio gerador e k suas mudanças cíclicas:

Vamos agora considerar como, usando o polinômio gerador g(x) = 1+x+x 3, a codificação é realizada com um código (7, 4). Tomemos, por exemplo, uma palavra de 4 bits (0101), que corresponde a um polinômio f(x) = x + x 3. Multiplicando esses dois polinômios.

Os códigos cíclicos são um tipo de códigos de grupo linear e pertencem a códigos sistemáticos. Eles foram originalmente criados para simplificar o procedimento de decodificação. No entanto, a alta eficiência de tais códigos na detecção de erros garantiu seu uso generalizado na prática. É conveniente considerar um vetor binário de código cíclico não como uma combinação de zeros e uns, mas como um polinômio de algum grau

onde x é a base do sistema numérico, coeficientes pertencentes ao conjunto no caso do sistema numérico binário.

Exemplo. Um vetor binário pode ser representado como um polinômio da seguinte forma:

Representar vetores binários na forma de polinômios nos permite reduzir operações em vetores a ações em polinômios. Em que:

a adição de polinômios é reduzida à soma do módulo de 2 coeficientes com potências iguais da variável

a multiplicação é realizada de acordo com a regra usual para multiplicar funções de potência, mas os coeficientes resultantes para uma determinada potência são somados módulo 2;

a divisão é realizada de acordo com as regras de divisão de funções de potência, e a operação de subtração é substituída pelo módulo de soma 2.

Exemplo. Encontre a soma dos polinômios

Encontre o produto de polinômios

Realizar divisão de polinômios

A principal propriedade dos códigos cíclicos é a seguinte: se um vetor pertence a um código cíclico, então qualquer vetor obtido daquele em consideração por meio de deslocamentos cíclicos também pertence a um código cíclico.

A ideia de construção de códigos cíclicos é baseada no conceito de polinômio irredutível. Um polinômio é chamado de irredutível se for divisível apenas por ele mesmo e por um, e não for divisível por nenhum outro polinômio. Em outras palavras, um polinômio irredutível não pode ser representado como um produto de polinômios de graus inferiores. Um polinômio é divisível por um polinômio irredutível sem resto. Polinômios irredutíveis desempenham o papel de gerar polinômios na teoria dos códigos cíclicos. Os tipos de polinômios irredutíveis de vários graus são dados em

Exemplos de polinômios irredutíveis:

Os vetores de código cíclico são construídos de acordo com as seguintes regras. Seja qualquer vetor binário de algum código natural; - monômio de grau polinômio irredutível de grau Então qualquer vetor de código cíclico é formado usando a relação

onde está o resto da divisão

Assim, qualquer vetor de código cíclico pode ser formado multiplicando um determinado vetor de código binário natural por um monômio de grau e adicionando o restante da divisão ao produto resultante. Ao construir códigos cíclicos usando o método indicado, a localização. Os bits de informação em cada vetor de código são estritamente ordenados - eles ocupam os bits mais altos do vetor de código e os dígitos restantes são de teste.

Exemplo. O vetor de código binário natural tem a forma Forme um vetor de código cíclico de negro, desde que o polinômio gerador tenha a forma

Vamos representar o vetor como um polinômio

Como resultado da divisão de um polinômio por um polinômio, obtemos o resto. É por isso

Um código cíclico, como qualquer código sistemático, é convenientemente especificado na forma de matriz usando uma matriz geradora da forma

onde está a matriz unitária transposta do formato - a matriz de dígitos de verificação formada pelo restante da divisão

Vamos definir a matriz geradora do código cíclico com o comprimento dos bits de informação e o polinômio gerador.

Obviamente, o modelo para a matriz geradora tem a forma

Para encontrar as linhas dos bits de verificação da matriz, calculamos e escrevemos cada vetor da matriz identidade como um polinômio

O comprimento do vetor de código cíclico é, portanto

(veja digitalização)

Como resultado, obtemos a matriz geradora C:

Qualquer vetor de um código cíclico é obtido como a soma da moda dos vetores de sua matriz geradora. Como o código cíclico é um grupo, o vetor zero é sempre atribuído ao código cíclico como o elemento unitário do grupo."

Tabela 13.5

Exemplo. Construa todos os vetores do código cíclico dado pela matriz geradora

O código é apresentado na tabela. 13.5.

Ressalta-se que cada código cíclico, especificado por uma determinada matriz geradora, pode ser representado em diversas versões, diferindo entre si no comprimento e na quantidade de bits de informação (com as mesmas capacidades de detecção). Estas variantes dos chamados códigos cíclicos encurtados são obtidas eliminando as últimas linhas e o mesmo número de colunas à esquerda na matriz geradora do código cíclico. Neste caso, o número de bits de verificação permanece inalterado, e o comprimento do código e o número de seus bits de informação são reduzidos respectivamente por um valor igual ao número de linhas e colunas riscadas da matriz geradora.

Exemplo, um código cíclico é dado por sua matriz geradora

Vamos riscar as últimas seis linhas e as primeiras seis colunas da esquerda. Obtemos a matriz geradora

As características (em termos de detecção de erros) do código resultante são as mesmas do código cíclico representado pela matriz geradora

A construção de códigos cíclicos com determinados parâmetros está associada à escolha de um polinômio gerador irredutível. O polinômio gerador é selecionado com base na seguinte condição: o grau do polinômio deve ser igual ao número de bits de verificação do código cíclico.

Na prática, muitas vezes surge a tarefa de construir um código cíclico de uma determinada potência e de determinadas capacidades de detecção e correção.

1. Como a potência do código cíclico é dada, o número de seus bits de informação é determinado de acordo com a fórmula

2. O número ideal de dígitos de verificação do código cíclico é determinado usando tabelas especiais.

3. Usando livros de referência, todos os polinômios de grau irredutíveis são encontrados

4. Para um dos polinômios não condutores (deve-se escolher o polinômio com maior número de termos) de grau, constrói-se uma matriz geradora do código cíclico. Cada vetor de código é calculado usando a fórmula

onde é o polinômio do vetor de informação da matriz geradora; - monômio de grau - resto da divisão

5. A matriz geradora construída é verificada quanto às seguintes condições:

a) o peso no sentido de Hamming de qualquer vetor da matriz geradora deve satisfazer a relação onde é a distância mínima, no sentido de Hamming, do código cíclico em consideração;

b) o peso no sentido de Hamming do vetor de verificação, que é a soma módulo 2 de quaisquer dois vetores de verificação da matriz geradora, deve satisfazer a relação

6. Se a matriz geradora do código cíclico satisfaz todas as condições acima, então todos os vetores do código cíclico são escritos e determinados de acordo com as regras conhecidas para códigos de grupos lineares. Caso o código não atenda aos requisitos, outro polinômio gerador de mesmo grau é selecionado e o procedimento de geração de um código cíclico é repetido para o novo polinômio.

Vamos construir um código cíclico com potência 16 e capacidade de correção

Pois determinamos o valor por

3" Usando livros de referência, encontramos todos os polinômios de grau irredutíveis. Existem dois desses polinômios:

4. Escolhemos um polinômio como gerador. O modelo da matriz geradora do código cíclico tem a forma.

Representamos cada vetor de informação da matriz como um polinômio

Determinamos completamente todos os vetores da matriz geradora usando a fórmula

Como o comprimento do vetor de código cíclico (veja o formato da matriz geradora então

Da mesma forma, encontramos todos os outros vetores da matriz geradora

Tabela 13.6

Como resultado, a matriz geradora C é obtida? código cíclico

5. A matriz geradora resultante satisfaz todas as condições necessárias. Portanto, construímos um código cíclico completo (Tabela 13.6). Como segue na tabela, o código atende, ou seja, satisfaz os requisitos da tarefa.

Notas. Ao utilizar um polinômio irredutível como gerador, obtemos um código que também satisfaz os requisitos do problema. Sua matriz geradora tem a forma

A detecção de erros usando códigos cíclicos é realizada da seguinte forma. Qualquer vetor de código cíclico é dividido por um polinômio gerador sem resto. Portanto, o critério para a presença de um erro em um vetor de código cíclico é o aparecimento de um resto diferente de zero da divisão do vetor de código cíclico por um polinômio gerador. Um resto diferente de zero é um identificador de um erro em um vetor de código cíclico, mas sua aparência não indica a localização do erro no vetor de código. A correção de erros é baseada no seguinte algoritmo:

1. Divida o vetor de código recebido por um polinômio gerador.

Se o número de uns não exceder a capacidade de correção do código, adicione o módulo 2 do vetor recebido com o restante resultante. O resultado da soma fornecerá o vetor de código corrigido. Se o número de unidades restantes for maior que a capacidade de correção do código, então desloque ciclicamente o vetor distorcido para a esquerda em um bit e depois divida pelo polinômio gerador. Se o restante resultante contiver unidades que não excedam a capacidade de correção do código cíclico, some o vetor deslocado ciclicamente com o restante. O resultado da soma é deslocado ciclicamente um dígito para a direita. O vetor resultante não contém mais erros e é um vetor de código cíclico.

3. Se após o primeiro deslocamento cíclico e divisão subsequente o resto contiver mais unidades do que a capacidade de correção do código, repita o procedimento do algoritmo até obter um resto com um número de unidades que não exceda a capacidade de correção do código. Neste caso, o resultado do último deslocamento cíclico é somado com o restante e o vetor resultante é deslocado ciclicamente tantos bits para a direita quanto o vetor original recebido com erro foi deslocado para a esquerda. O resultado é um vetor de código corrigido.

Seja o código cíclico dado por sua matriz geradora C e polinômio gerador, onde

O código tem valor 3, ou seja, corrige erros de multiplicidade Seja aceito o vetor 0011101 em vez do vetor 0001101. Para corrigir o erro, realizamos as seguintes ações. Escrevemos o vetor resultante como um polinômio: então dividimos por

O restante obtido como resultado da divisão contém três unidades, o que é mais do que a capacidade corretiva do código. Portanto, fazemos um deslocamento cíclico para a esquerda em um bit do vetor de código recebido. Como resultado temos

Nós dividimos por

O restante resultante contém duas unidades, o que é maior que a capacidade de correção do código. Portanto, fazemos outro deslocamento cíclico para a esquerda em um bit do vetor de código recebido. Como resultado temos

Nós dividimos por

O resto resultante contém novamente duas unidades, então fazemos outro deslocamento cíclico uma casa para a esquerda e obtemos Dividir por

Uma classe de códigos lineares chamada códigos shaic. O nome vem da propriedade principal desses códigos: se uma determinada combinação de códigos pertence a um código cíclico, então a combinação obtida pela permutação cíclica da combinação original (deslocamento cíclico) também pertence a este código:

A segunda propriedade de todas as combinações permitidas de códigos cíclicos é sua divisibilidade sem resto por algum polinômio selecionado, denominado gerador.

Essas propriedades são utilizadas na construção de códigos para codificação e decodificação de dispositivos, bem como na detecção e correção de erros.

Os códigos cíclicos são toda uma família de códigos resistentes a erros (uma das variedades dos quais são os códigos de Hamming), proporcionando maior flexibilidade em termos de capacidade de implementação de códigos com a capacidade necessária para detectar e corrigir erros que surgem durante a transmissão de combinações de códigos. um canal de comunicação. Um código cíclico refere-se a códigos de bloco sistemático (l, &) nos quais Para os primeiros dígitos representam uma combinação do código primário, e os subsequentes (l - Para) dígitos são verificação.

A construção de códigos cíclicos baseia-se na operação de divisão da combinação de códigos transmitidos pelo polinômio de grau irredutível gerador G. O restante da divisão é usado para formar dígitos de verificação. Neste caso, a operação de divisão é precedida por uma operação de multiplicação, que desloca a combinação do código de informação de ^ bits para a esquerda em G descargas.

Ao decodificar a combinação de código de n bits recebida, a divisão é novamente realizada pelo polinômio gerador (gerador, formador).

A síndrome de erro nesses códigos é a presença de um resto quando a combinação de códigos recebida é dividida pelo polinômio gerador. Se a síndrome for igual a zero, considera-se que não há erros. Caso contrário, a partir da síndrome resultante, é possível determinar o número de dígitos da combinação de códigos recebida em que ocorreu o erro e corrigi-lo.

Porém, não se pode descartar a possibilidade de ocorrência de múltiplos erros nas combinações de códigos, o que pode levar a falsas correções e (ou) falha na detecção de erros na transformação de uma combinação permitida em outra.

Deixe o número total de bits no bloco ser igual a i, dos quais eles carregam informações úteis T bits, então em caso de erro é possível corrigir j bits. Dependência 5 de P E T para códigos pode ser determinado na tabela. 2.6.

Tabela 2.6

Dependência do número total de bits de combinações do número de informações e bits corrigidos

Aumentando a diferença (p-t), você não pode apenas aumentar o número de bits corrigidos é, mas também para detectar vários erros. As porcentagens de erros múltiplos detectados são fornecidas na Tabela. 2.7.

Tabela 2.7

Porcentagens de vários erros detectados

É conveniente descrever códigos cíclicos e construí-los usando polinômios (ou polinômios). Escrever uma combinação na forma de um polinômio é usado para exibir de forma formalizada a operação de deslocamento cíclico da combinação de código original. Assim, a “combinação de código de elemento pode ser descrita pelo polinômio (P- 1) graus:

Ondea„_j =(0, 1) euma“_, =0 corresponde a zero elementos da combinação, d„_, = 1 - diferente de zero;eu- número do dígito da combinação de código.

Vamos imaginar polinômios para combinações específicas de 4 elementos:

As operações de adição e subtração são equivalentes e associativas e são realizadas módulo 2:

Exemplos de execução de operações:

A operação de divisão é a divisão usual de polinômios, mas em vez de subtração, utiliza-se o módulo de adição 2:

Mudança cíclica de uma combinação de código - mover seus elementos da direita para a esquerda sem violar sua ordem, de modo que o elemento mais à esquerda tome o lugar do mais à direita.

As principais propriedades e nomes dos códigos cíclicos estão relacionados ao fato de que todas as combinações permitidas de bits na mensagem transmitida (palavras-código) podem ser obtidas deslocando ciclicamente alguma palavra-código fonte.

Vamos supor que a combinação de código original e o polinômio correspondente sejam dados:

Vamos multiplicar Oh) sobre X:

Desde o grau máximo X em uma combinação de código de comprimento P não excede (l - 1), então do lado direito da expressão resultante para obter o polinômio original é necessário subtrair Oh"-1). Subtração Oh"- 1) é chamado de módulo restante (x n - 1).

A mudança da combinação original por / medidas pode ser representada da seguinte forma: uma(x) ? VOCÊ - Oh"- 1), ou seja multiplicação Oh) x" e tomando o módulo restante (x" - 1). Tomar o resto é necessário para obter um polinômio de grau maior ou igual a P.

A ideia de construir códigos cíclicos baseia-se na utilização polinômios irredutíveis. Um polinômio irredutível é um polinômio que não pode ser representado como um produto de polinômios de graus inferiores, ou seja, é divisível apenas por si mesmo ou por um e não por qualquer outro polinômio. O binômio (x" + 1) é divisível por tal polinômio sem resto. Polinômios irredutíveis na teoria dos códigos cíclicos desempenham o papel de gerar polinômios.

Voltando à definição de código cíclico e levando em consideração o registro das operações de deslocamento cíclico de combinações de códigos, podemos escrever a matriz geradora do código cíclico na seguinte forma:

OndeP(x)- a combinação de código original com base na qual todos os outros são derivados(T- 1) combinações básicas;

C, = 0 ouCj =1 (“O” se o grau resultante do polinômioR(x)-x'não excede (l - 1), ou “1” - se exceder).

Combinação P(x)é chamada de combinação geradora (gerador). Para construir um código cíclico, basta escolher corretamente P(x). Então, todas as outras combinações de códigos são iguais às do código do grupo.

O polinômio gerador deve atender aos seguintes requisitos:

• P(x) deve ser diferente de zero;
• peso P(x) não deve ser inferior à distância mínima do código: V(P(x)) > d mm ;
• P(x) deve ter o grau máximo k (k - número de elementos redundantes no código);
• P(x) deve ser um divisor do polinômio (x" - 1).

O cumprimento da última condição leva ao fato de que todas as combinações de código de trabalho do código cíclico adquirem a propriedade de serem divisíveis por P(x) sem deixar vestígios. Levando isso em consideração, podemos dar outra definição de código cíclico: um código cíclico é um código cujas todas as combinações de trabalho são divisíveis pelo polinômio gerador sem resto.

Para determinar o grau do polinômio gerador, você pode usar a expressão r > log 2 (e + 1), onde P- tamanho do pacote transmitido por vez, ou seja, comprimento do código cíclico que está sendo construído.

Exemplos de geração de polinômios são fornecidos na Tabela. 2.8.

Tabela 2.8

Exemplos de geração de polinômios

O algoritmo para obter uma combinação de código cíclico permitida a partir de uma combinação de código simples é o seguinte.

Seja dado um polinômio P(x) = a g _ ( x g + a g _ 2 x g ~ 1 + ... + 1, que determina a capacidade de correção do código e o número de bits de verificação Para, bem como a combinação original de um código elementar simples e bits de informação na forma de um polinômio Umt(x).

É necessário determinar a combinação de código cíclico permitida (e, Para).

• 1. Representamos a combinação de código original como um polinômio Umt(x). Multiplique o polinômio da combinação de código original por x g: A t (x) x g. Grau do polinômio gerador G igual ao valor do bit mais significativo da combinação de código original.
• 2. Definimos os bits de verificação que complementam a combinação de informação original à permitida, como o restante da divisão do produto obtido no parágrafo anterior pelo gerador

polinomial:

Denotamos o resto da divisão como R(x).

3. Combinação de código cíclico finalmente resolvida

o código será definido como = E t(x)? xr + R(x).

Para determinar erros na combinação de código recebida, basta dividi-la pelo polinômio gerador. Se a combinação aceita for legal, o restante da divisão será zero. Um resto diferente de zero indica que a combinação aceita contém erros. Com base no tipo de resíduo (síndrome), em alguns casos também é possível tirar uma conclusão sobre a natureza do erro e sua localização e corrigir o erro.

O algoritmo de detecção de erros é o seguinte.

Deixe "combinações de elementos ( n = k + t).

• 1. Identificamos a presença de um erro. Obtemos o resto da divisão da combinação aceita Um n -(x) para o polinômio gerador P(x): UMA(X)
• --- = Rq(x). Disponibilidade de saldo R0(x) em (L 0 (x) f 0) indica P(x)

sobre o erro.

2. Divida o polinômio resultante #(x) = L'_,(X) 0 Rq (x) para o gerador R g (x): W-1 = R(x), Onde R(x)- saldo atual.

3. Compare LDx) e R(x). Se forem iguais, o erro ocorreu no bit mais significativo. Caso contrário, aumente o grau do polinômio aceito por x e divida novamente:

4. Compare o resto resultante com Rq(x). Se forem iguais, o erro ocorreu no segundo dígito. Se não forem iguais, multiplique Shchh) x 2 e repita essas operações até obter

R(x) = inferno.

O erro estará no dígito correspondente ao número pelo qual o grau é aumentado Shchh), mais 1. Por exemplo, em caso de igualdade R(x) e LDx)

Correspondente a esta palavra, de uma variável formal x. Pode-se ver que esta correspondência não é apenas biunívoca, mas também isomórfica. Como as “palavras” consistem em letras do campo, elas podem ser somadas e multiplicadas (elemento por elemento), e o resultado estará no mesmo campo. Um polinômio correspondente a uma combinação linear de um par de palavras e é igual a uma combinação linear de polinômios dessas palavras

Isso nos permite considerar o conjunto de palavras de comprimento n sobre um corpo finito como um espaço linear de polinômios com grau no máximo n-1 sobre o corpo

Descrição algébrica

Se uma palavra-código obtida deslocando ciclicamente um bit para a direita da palavra, então seu polinômio correspondente c 1 (x) é obtido do anterior multiplicando por x:

Aproveitando o fato de que

Desloque para a direita e para a esquerda respectivamente por j classificações:

Se eu(x) - polinômio arbitrário sobre o campo GF(q) E c(x) - palavra de código de cíclico ( n,k) código, então eu(x)c(x)euód(x n − 1) também a palavra-código para este código.

Gerando polinômio

Definição O polinômio gerador do cíclico ( n,k) código C tal polinômio diferente de zero é chamado de C, cujo grau é o menor e o coeficiente do maior grau g R = 1 .

Teorema 1

Se C- cíclico ( n,k) código e g(x) é seu polinômio gerador, então o grau g(x) é igual R = n − k e cada palavra de código pode ser representada exclusivamente na forma

c(x) = eu(x)g(x) ,

onde está o diploma eu(x) menos que ou igual a k − 1 .

Teorema 2

g(x) - gerando polinômio de cíclico ( n,k) o código é um divisor do binômio x n − 1

Consequências: assim, qualquer divisor polinomial pode ser escolhido como um polinômio gerador x n−1. O grau do polinômio escolhido determinará o número de símbolos de teste R, número de símbolos de informação k = n − R .

Matriz geradora

Os polinômios são linearmente independentes, caso contrário eu(x)g(x) = 0 para diferente de zero eu(x) o que é impossível.

Isto significa que as palavras de código podem ser escritas, como acontece com os códigos lineares, da seguinte forma:

, Onde Gé matriz geradora, eu(x) - informativo polinomial.

Matriz G pode ser escrito de forma simbólica:

Verifique a matriz

Para cada palavra-código de um código cíclico, . É por isso verificar matriz pode ser escrito como:

Codificação

Assistemático

Com a codificação não sistemática, a palavra-código é obtida na forma do produto de um polinômio de informação e um polinômio gerador

c(x) = eu(x)g(x) .

Pode ser implementado usando multiplicadores polinomiais.

Sistemático

Com a codificação sistemática, a palavra-código é formada na forma de um subbloco de informação e uma verificação

Deixe a palavra de informação formar potências superiores da palavra de código, então

c(x) = x R eu(x) + é(x),R = n − k

Então da condição segue

Esta equação estabelece a regra para a codificação sistemática. Pode ser implementado usando filtros lineares multiciclo (MLFs)

Exemplos

Código binário (7,4,3)

Como divisor x 7 − 1 escolhemos um polinômio gerador de terceiro grau g(x) = x 3 + x + 1 , então o código resultante terá o comprimento n= 7, número de símbolos de teste (grau de geração de polinômio) R= 3, número de símbolos de informação k= 4, distância mínima d = 3 .

Matriz geradora código:

,

onde a primeira linha é a notação polinomial g(x) coeficientes em ordem crescente. As linhas restantes são mudanças cíclicas da primeira linha.

Verifique a matriz:

,

onde a i-ésima coluna, começando em 0, representa o restante da divisão x eu para um polinômio g(x) escrito em ordem crescente, começando de cima.

Assim, por exemplo, obtém-se a 3ª coluna, ou em notação vetorial.

É fácil verificar que GH T = 0 .

Código BCH binário (15,7,5)

Como um polinômio gerador g(x) você pode escolher o produto de dois divisores x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Então cada palavra de código pode ser obtida usando o produto do polinômio de informação eu(x) com diploma k− 1 assim:

c(x) = eu(x)g(x) .

Por exemplo, a palavra de informação corresponde ao polinômio eu(x) = x 6 + x 5 + x 4 + 1 , então a palavra de código c(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , ou em forma vetorial

Veja também

Ligações

Fundação Wikimedia. 2010.

• Formas cíclicas na música
• Condições de contorno cíclicas

Veja o que são “códigos cíclicos” em outros dicionários:

códigos cíclicos encurtados- - [L.G. Dicionário Inglês-Russo de tecnologias de informação. M.: State Enterprise TsNIIS, 2003.] Tópicos tecnologia da informação em geral EN códigos cíclicos encurtados ...

Códigos Reed-Solomon- códigos cíclicos não binários que permitem corrigir erros em blocos de dados. Os elementos do vetor de código não são bits, mas grupos de bits (blocos). Os códigos Reed Solomon que funcionam com bytes (octetos) são muito comuns. O código de Reed Solomon é ... Wikipedia

Códigos Golay- Uma família de códigos de blocos lineares perfeitos com correção de erros. O mais útil é o código binário de Golay. O código ternário de Golay também é conhecido. Os códigos de Golay podem ser considerados códigos cíclicos. … … Guia do Tradutor Técnico

Códigos de correção de erros

Códigos de correção de erros- Detecção de erros na tecnologia de comunicação, ação que visa monitorar a integridade dos dados no momento da gravação/reprodução de informações ou na sua transmissão por linhas de comunicação. Procedimento de correção de erros (correção de erros) para restaurar informações após... ... Wikipedia

Códigos de correção de erros- Detecção de erros na tecnologia de comunicação, ação que visa monitorar a integridade dos dados no momento da gravação/reprodução de informações ou na sua transmissão por linhas de comunicação. Procedimento de correção de erros (correção de erros) para restaurar informações após... ... Wikipedia