Código descrambler-scrambler detector e
corretor de erros e seu uso em equipamentos
Vectura
Victor Alfonso Valenzuela Diaz*, Isabela Vasconcelos de Carvalho Motta
Este artigo descreve um novo código corretor de erros baseado em uma estrutura descramblerscrambler. Descreve também sua modelagem em termos de grafos-fatores. Esse código corresponde a
uma evolução do código descrambler-scrambler que foi anteriormente desenvolvido para os
equipamentos Vectura1. São inicialmente descritos os conceitos básicos e a motivação do uso de códigos
corretores e detectores de forma geral e, em particular, na transmissão interna de equipamentos.
Posteriormente, são descritos o tipo de código detector de erro e o novo código corretor de erros.
Finalmente, é feita a análise do uso da técnica de grafos-fatores para modelar esse código. Durante a
apresentação dos códigos detector e corretor, é analisada a eficiência destes utilizando uma abordagem
baseada nas características das sequências pseudoaleatórias de máximo comprimento.
Palavras-chave: Código detector de erro. Código corretor de erros. Grafos-fatores. Scrambler.
Descrambler.
Introdução
Os sistemas de transmissão digital, apesar de
apresentarem maior imunidade a ruídos do que
os
sistemas
analógicos,
frequentemente
precisam conviver com taxas de erros de
transmissão não nulas. Nesses sistemas de
transmissão ruidosos, o uso de códigos
detectores e corretores de erro pode ser a
melhor solução para obter taxas de erro baixas a
custos adequados. O código detector de erros
descrambler-scrambler foi concebido inicialmente
para ser usado na transmissão interna de sinais
entre processadores da plataforma Trópico
(VALENZUELA, 1987). Posteriormente, passou a
ser usado também em equipamentos da
plataforma Vectura. Hoje, esses equipamentos
possuem uma arquitetura com controle
distribuído baseada em uma rede composta de
vários processadores e tratam mais de 45
bilhões de minutos de chamadas por mês,
exigindo requisitos de altíssima qualidade na sua
rede de processadores interna. Além de revisitar
esse código, é também apresentada uma
metodologia de análise de probabilidade de falha,
ou seja, de não detecção de erros.
Posteriormente foi desenvolvido o código corretor
de erros descrambler-scrambler, que é também
apresentado neste artigo.
1 Código detector de erro descramblerscrambler
Os códigos detectores e corretores de erro aqui
tratados se aplicam a sinais digitais que, em
geral, possuem taxas de bits constantes. De fato,
pode-se abstrair a representação física (elétrica,
por exemplo, e inclusive temporal) desses sinais
e considerá-los simplesmente sequências de bits
“1s” e “0s”. Uma característica importante do
código é que não há exigência de que todas as
mensagens originais possuam um mesmo
tamanho.
O código detector descrambler-scrambler foi
desenvolvido para ter uma implementação
extremamente simples (e confiável). Por esse
motivo optou-se inicialmente por um código
detector e não corretor de erros.
1.1 Sequências de comprimento máximo
O código detector de erro descrambler-scrambler
tem seu conceito básico relacionado com as
sequências de comprimento máximo (Maximum
Length Sequences – MLS). MLS são sequências
periódicas que pertencem à classe de
sequências binárias pseudoaleatórias.
As sequências MLS são geralmente geradas a
partir de shift-registers com realimentações
lineares
(PETERSON;
WELDON,
1961).
Considere um shift-register, ou registrador de
deslocamento, que possui uma entrada e d = 7
saídas e as saídas 3 e 7 realimentadas através
de “ou-exclusivo” na sua entrada.
O operador “ou-exclusivo” de k entradas tem sua
saída igual a 1, se o número de entradas em “1”
for ímpar, e tem sua saída igual a zero, se esse
número de entradas em “1” for par. Se as
realimentações (ou taps) do registrador forem
escolhidas adequadamente, a sequência gerada
será uma sequência de comprimento máximo
*Autor a quem a correspondência deve ser dirigida: [email protected]
1 Os equipamentos Vectura são desenvolvidos no escopo do Projeto CONVERTE – Apoio da FINEP com recursos do FUNTTEL.
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
register do mesmo tamanho e com as
mesmas realimentações que a primeira), mas
deslocada de i bits da primeira, com i sendo
não múltiplo do período da sequência. A soma
em “ou-exclusivo” das duas sequências é
igual à mesma sequência MLS, mas com um
atraso j, em que j é diferente de zero e
diferente de i. A Figura 1 mostra esse
comportamento. Considerou-se a primeira
sequência com defasagem 0.
(MLS). Isso significa que será uma sequência
periódica que se repete a cada 2 d - 1 períodos de
bit, onde "d" é o número de posições do
registrador.
Dessa forma, pode-se escrever:
S.∆0 = S.∆3 ⊕ S.∆7
Fazem parte dessa expressão o operador de
atraso ∆, as funções produto (por exemplo em S.
∆0) e a soma módulo 2 (“ou-exclusivo”). Nessa
matemática, as variáveis (valores de S) podem
assumir unicamente os valores 0 e 1
(correspondentes ao Campo de Galois GF (2)).
Os sistemas desenvolvidos dentro dessa
matemática são lineares (ZUFFO, 1974).
Pode ser mostrado (GOLOMB, 1967) que, para
que a sequência gerada pelo registrador seja
uma
MLS,
as
realimentações
devem
corresponder a um polinômio primitivo em GF
(2).
As
sequências
MLS
possuem
várias
propriedades interessantes. Entre elas, as
seguintes são importantes neste trabalho:
• O número de bits “1” em um período (de 2d -1
bits) é igual a um mais o número de bits “0”.
Ou seja, temos 2d -1 bits “1” e “2d-1 -1” bits “0”.
Dependendo do conteúdo inicial do
registrador, a sequência é iniciada em um
ponto diferente, mas sempre é gerada a
mesma sequência de período “2d-1” bits. Uma
particularidade é quando o registrador tem
conteúdo inicial com todos os bits iguais a
zero. Nesse caso, o registrador não sai desse
estado e a sequência gerada é uma
sequência de zeros.
•
Considere uma sequência MLS e outra
sequência MLS igual (gerada por um shift-
Defasagem j da terciera seqüência MLS
•
•
Como pode ser visto na Figura 1, a
defasagem da terceira MLS se distribui de
forma esparsa. Em uma aproximação
pseudoestatística pode ser considerado que a
defasagem j da MLS, resultante da soma de
MLSs com defasagens 0 e i, se distribui de
forma aleatória e uniforme, entre 1 e 2d -1.
•
Por extensão, a soma de 3 ou mais versões
da mesma MLS, defasadas entre si, é igual à
mesma MLS com uma outra defasagem.
1.2 Scrambler-descrambler
Em função de suas propriedades de
pseudoaleatoriedade, as sequências MLS
possuem varias aplicações. Uma variação
dessas sequências, em que a máquina de estado
passa a receber sinais de entrada externos, é o
do embaralhador (scrambler) e desembaralhador
(descrambler) de sinais. Como no caso das
sequências MLS, esses circuitos utilizam
também registradores com realimentações
lineares realizadas a partir de “ou-exclusivos”.
Em algumas aplicações, é conveniente que os
sinais transmitidos não possuam sequências
grandes de bits “1” ou bits “0”. Nesses casos,
podem ser usadas configuração scrambler do
120
100
80
60
40
20
0
0
20
40
60
80
100
120
Defasagem i da segunda seqüência MLS
Figura 1 Defasagem da MLS resultante da soma de duas MLSs defasadas de i
50
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
SB = SA ⊕ ST. ∆3 ⊕ ST. ∆7 ⊕ ST. ∆3 ⊕ ST. ∆7
palavra de "d" bits, mas sempre deve ser usada a
mesma palavra. O tamanho e conteúdo dessa
palavra independem da quantidade “b” de bits da
sequência original. Sem perda de generalidade,
vamos considerar que essa palavra seja igual a
todos os bits iguais a “1”. Após o acréscimo
desses "d" bits, o sinal é aplicado ao codificador
(descrambler), conforme Figura 3. No início de
cada mensagem, os shift-registers do codificador
e do decodificador devem ser levados à mesma
condição inicial. Por convenção, definiu-se que
essa condição é a palavra com todos os bits
iguais a “0”.
No exemplo da Figura 3, as equações
polinomiais que representam esse circuito são:
ou seja,
ST = SA ⊕ SA. ∆3 ⊕ SA. ∆7
SB = SA
SB = ST ⊕ SB. ∆3 ⊕ SB. ∆7
lado da transmissão e descrambler no lado da
recepção, conforme Figura 2.
Tanto o descrambler como o scrambler utilizam
shift-registers com realimentações lineares. No
entanto, nessa configuração, os dois circuitos
possuem sinais de entrada: SA no caso do
scrambler e ST no caso do descrambler.
Pode ser verificado no exemplo da Figura 2 que:
ST = SA ⊕ ST. ∆3 ⊕ ST. ∆7
SB = ST ⊕ ST. ∆3 ⊕ ST. ∆7
CLK
Scrambler
SB = SA ⊕ SA. ∆3 ⊕ SA. ∆7 ⊕ SB. ∆3 ⊕ SB. ∆7
ou seja,
SB. (1 ⊕ ∆3 ⊕ ∆7) = SA. (1 ⊕ ∆3 ⊕ ∆7)
SA
e, portanto,
SB = SA
CLK
Descrambler
SB
Figura 2 Configuração scrambler-descrambler
1.3 O código descrambler-scrambler
O código descrambler-scrambler (VALENZUELA,
1987) é um código polinomial no qual o sinal
original (source sequence) é fornecido ao
codificador em blocos. Esse código permite que
cada bloco tenha um comprimento diferente,
sendo necessário para isso que o decodificador
saiba em que ponto inicia e em que ponto
termina cada bloco. Para efeito de análise,
considere-se um comprimento genérico de “b”
bits.
Nesse código, no codificador, que passa a ser o
descrambler, é acrescentada uma palavrapadrão de “d” bits fixos imediatamente após os
“b” bits. Esses "d" bits podem ser qualquer
Isso significa que, assim como no caso
scrambler-descrambler, a saída SB é igual à
entrada SA, o que também vale para qualquer
outro polinômio P (∆), desde que usado tanto no
codificador como no decodificador. O sinal ST
também apresenta um embaralhamento, porém
menor do que no caso scrambler-descrambler.
De fato, cada bit do sinal SA afeta o sinal ST,
unicamente, cada vez que passa por uma das
realimentações do registrador. Isso não é
problema, pois o objetivo do código não é obter o
embaralhamento do sinal transmitido. No caso
em que o scrambler é usado na transmissão, o
sinal ST é mais embaralhado, pois a informação
dos bits do sinal SA, como faz parte da
realimentação, fica em “loop eterno” no
registrador. Exatamente por causa dessa
propriedade, nesse código o scrambler é usado
no decodificador. No caso de ocorrência de um
ou mais erros de bit na transmissão, esses bits
errados entram no loop de realimentações do
shift-register e se propagam até o final do bloco,
ou seja, até os últimos "d" bits. Se é encontrada
uma palavra diferente da palavra original de
verificação (que por convenção é “todos os bits
iguais a 1”), o erro é detectado. O fato de o
polinômio usado ser primitivo, além de implicar
em um efeito melhor de propagação do erro,
diminui as probabilidades de não detecção,
conforme indicado mais adiante.
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
51
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
Descrambler (Codificador)
SF
Insere “d”
bits fixos no
fim de cada
bloco
SA
ST
Scrambler (Decodificador)
SS
Retira “d” bits
fixos no fim de
cada bloco
Detecta e informa
ocorrência de
erros
SB
Informa mensagem com erro
Figura 3 Codificador e decodificador descrambler-scrambler
1.4 Análise no caso de presença de erro de
transmissão
Para avaliar a eficiência desse código, é
importante calcular a probabilidade de não
detecção dos erros. Pode ser facilmente provado
que, na ausência de erros, existe uma relação
biunívoca entre o conjunto de possíveis
mensagens em SA e o conjunto de possíveis
mensagens em ST. Isso significa que, tomando
m como o número de bits na mensagem
codificada (m = b + d) para cada uma das 2 m-d
possíveis mensagens em SA, existe uma e
somente uma mensagem em ST, e vice-versa.
Na presença de erros, o sinal recebido de SR é
diferente de STE e tem-se, na entrada do
decodificador, uma sequência “ST com erros”
denominada STE.
Um erro não será detectado unicamente se a
mensagem com erro em STE corresponder a
uma das mensagens permitidas em ST e,
portanto, for esperada em SR. Nesse caso, a
mensagem (após decodificação) corresponderá
a uma mensagem permitida em SB, mas não a
uma mensagem correta. Então, se todos os tipos
de erro têm a mesma probabilidade, a
probabilidade condicional de um erro não ser
detectado, dado que houve erro, é (onde os
termos -1 no numerador e denominador
correspondem à exclusão da mensagem
52
correta):
P (erro não detectado/erro existe) =
(2m-d- 1) /(2m
≅ 2-d - 2-m ≅ 2-d para m >> d.
Portanto, nesse caso, a probabilidade de haver
um erro não detectado diminui exponencialmente
com o aumento de "d" e é praticamente
independente de m, desde que m>>d. É
interessante estabelecer, para cada quantidade
de bits errados por mensagem, a probabilidade
do erro não ser detectado.
A Figura 4 mostra um modelo em que o processo
de ocorrência de erros é representado por uma
sequência de erro SE somada (em “ouexclusivo”) com a sequência ST. Nos períodos
de bit em que SE = 1, o bit correspondente de ST
é invertido, provocando o erro. Essa soma com o
sinal SE corresponde ao modelo do canal de
transmissão. Note que está se abstraindo o
atraso de transmissão e pressupondo que no
lado da recepção há uma infraestrutura de timing
que permite trabalhar em sincronismo com o lado
de transmissão. O canal é considerado do tipo
sem memória, dado que a distribuição de
probabilidades atribuídas para o erro em cada bit
é considerada independente do histórico de
símbolos transmitidos anterior e posteriormente.
Denominando-se o sinal na saída do
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
decodificador de SB, no caso de ausência de
erro, e SBE, no caso de presença de erro,
obtêm-se as expressões:
Na ausência de erro: SB = ST ⊕ SB. P (∆)
Na presença de erro: SBE = STE ⊕ SBE. P (∆)
em que P (∆) é o polinômio gerador. Somando as
duas expressões tem-se:
SB ⊕ SBE = (ST ⊕ STE) ⊕ (SB ⊕ SBE). P (∆)
Denomina-se SB ⊕ SBE = SER. SER é, portanto,
a sequência de erros observada na saída do
decodificador. Ou seja, SER é uma sequência
que possui bits “1” nos intervalos de bit, onde SB
apresenta erros, ou seja, onde é diferente de SA.
Como STE = ST ⊕ SE, então SER = SE ⊕ SER.
P (∆).
Descrambler (Codificador)
SA
lineares, pode ser analisado o comportamento
separado do scrambler contendo as sequências
ST e SE como entradas de dois circuitos iguais,
conforme Figura 5.
Note que se trata de uma representação teórica,
pois na prática não se conhece SE e sim,
unicamente, sua soma com ST (sinal STE). No
entanto, isso nos permite fazer, em termos de
comportamento da taxa de erros, uma análise
separada para os sinais de erro. Em
correspondência a cada mensagem enviada pelo
codificador (bloco de m = b+d bits), pode-se
considerar que há mensagens do mesmo
tamanho em SE e SER. Nos casos sem erro, as
duas mensagens SE e SER têm todos os seus
bits iguais a zero.
Mensagens
com
erro
não
detectado
correspondem a mensagens SE que não têm
todos os seus bits iguais a zero, mas que
provocam mensagens em SER com seus últimos
"d" bits iguais a zero.
1.4.1
ST
SE
Canal de
transmissão
SR = STE
Scrambler (Decodificador)
SB
Figura 4 Representação de canal de transmissão
ruidoso
Essa relação entre SER e SE é a mesma
relação existente entre SB e ST. Isso significa
que, se a sequência SER for aplicada ao
descrambler, sua sequência de saída deverá ser
SE, e se a sequência SE for aplicada ao
scrambler, a sequência de saída deverá ser SER.
Essa conclusão é muito interessante, mostrando
que, em uma relação efeito-causa (em
contraposição a causa-efeito), a partir do sinal
SER, pode ser obtido o sinal SE (que provocou o
sinal SER).
A sequência STE, na entrada do scrambler
(decodificador) é igual à soma das duas
sequências ST e SE. Por se tratar de circuitos
Erros simples não detectados
Todos os erros simples (ou seja, com um único
bit = 1 na mensagem em SE) são detectados por
esse código. Isso pode ser provado considerando
a relação SER = SE ⊕ SER. P (∆) da seguinte
forma: dado que o conteúdo inicial do registro é,
por convenção, formado por todos os bits iguais
a “0”, enquanto a sequência SE não apresenta
seu único bit “1”, seu conteúdo permanecerá com
todos os bits iguais a zero, porque nessa
situação o scrambler se comporta como um
gerador de sequência MLS em seu estado de
fuga “todos os bits iguais a zero”.
No instante em que o único bit “1” da mensagem
SE ocorre, o registrador passa ao estado em que
sua primeira entrada é 1 e todas as outras 0.
Desse ponto em diante, a sequência SE volta a
zero e o scrambler passa a se comportar como
um gerador de sequência MLS que nunca volta
ao estado “tudo 0”. Isso significa que no instante
de detecção, no fim da mensagem, o registro
terá um conteúdo diferente da palavra-padrão
esperada.
1.4.2
Erros duplos
A análise de erro duplo pode ser realizada
considerando as propriedades de separação
linear (como a ilustrada na Figura 5). A
sequência SE, que nesse caso possui dois bits
“1” em sua mensagem, pode ser considerada a
soma (em “ou-exclusivo”) de duas sequências
SE1 e SE2, cada uma com um único bit “1”, e
pode ser usado um raciocínio semelhante ao da
análise de erro simples.
A única situação em que a palavra de "d" bits no
fim da mensagem transmitida pode ser
mascarada, implicando em um erro não
detectado, é com conteúdos dos registros
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
53
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
relativos a SE1 e a SE2 iguais nos últimos "d"
bits da mensagem, pois somente assim sua
soma se anulará. Isso significa que as
sequências MLS ativadas pelos bits “1” em SE1 e
SE2 devem estar em fase, o que somente pode
ocorrer se a distância entre esses bits “1” em
SE1 e SE2 for um múltiplo do período p = 2 d -1
bits da MLS. Pode ser verificado que o número
N2 de erros duplos que não podem ser
detectados é (considerando I = Int [m/p]):
Para m ≤ 2d -1 N2 = 0;
Para m > 2d -1 N2 =
 I + 1
I 
 + [( I + 1). p − m].  =
( m − I . p )
 2 
2
=
I [2.m − ( I + 1). p]
2
ST
SB
SE
SBE
SER
Figura 5 Separação linear
Supondo-se, como exemplo, que as mensagens
usadas em um dado sistema têm comprimento
máximo de b = 512 bytes, ou seja 4.096 bits, se
for usada uma palavra de verificação de d = 16
bits tem-se:
m = b+d = 4.096+16 = 4.112 < 65.535 = 216 -1
Ou seja, não haverá mensagens com erro duplo
não detectadas.
No entanto, se o registrador tiver d = 7 bits,
usando a expressão para m > 2d -1, obtêm-se
que o número de mensagens com dois erros não
detectados é 64.240 mensagens com dois erros
não detectadas. De acordo com a (função)
Combinação {4.103;2} = 8.415.253 erros duplos
possíveis, não será detectado um de cada
8.415.253 / 64.240 = 130,997 erros duplos. Note
que esse valor se aproxima de um a cada 2d.
Considerando que todos os possíveis erros
duplos têm a mesma probabilidade, tem-se:
Prob (erro duplo não detectado/ocorreu erro
duplo) =
=
I [2.m − ( I + 1). p]
m.(m-1)
1.4.3
Erros de distância maior que dois
Para o caso de mais de dois erros em uma
mensagem, a quantidade de erros não
detectados depende do polinômio primitivo usado
nas realimentações dos shift-registers. Como
indicado anteriormente, a soma de duas versões
da mesma sequência MLS defasadas de i bits,
sendo i não múltiplo do período da sequência, é
igual a uma terceira versão da mesma MLS, que
não se encontra em fase com nenhuma das duas
anteriores. O mesmo vale para a soma de mais
de duas sequências MLS.
Eventualmente, as fases podem ir se compondo
de forma que a soma de todas as MLS, menos a
última, seja uma MLS que esteja exatamente em
fase com essa última. Nesse caso, a soma final
será uma sequência que terá todos os bits iguais
a zero a partir do início da última MLS.
Exatamente, esse é o caso em que a ocorrência
de mais de dois erros na mensagem provoca a
não identificação de erros realizada com base
nos "d" últimos bits da mesma.
Quando o número de erros na mensagem é
maior ou igual a 3, torna-se difícil fazer uma
determinação analítica da quantidade de erros
não detectados. Em vez disso, para verificar
como é esse comportamento, exercitaram-se
exaustivamente
(considerando
todas
as
situações possíveis) alguns casos de código
descrambler-scrambler.
Para facilitar esses cálculos, utilizaram-se mais
uma vez as propriedades lineares. Conforme a
relação SE = SER ⊕ SER. P (∆), a partir do sinal
SER (efeito) pode ser gerado o sinal SE (causa),
que provocou o sinal SER.
Com o objetivo de gerar todas as possíveis
mensagens de erro em SER não detectadas,
para um decodificador com mensagens de m =
22 bits relativos a b = 15 de sequência original
mais d = 7 de palavra-padrão (todos os bits
iguais a zero), foram geradas todas as possíveis
mensagens em SER que possuem 15 bits
(exceto a mensagem todos os bits iguais a zero –
pois ela corresponde ao caso sem erro) e
finalizam com 7 zeros (e, portanto, não são
detectadas). O fato de a mensagem SER ter
todos os últimos 7 bits iguais a zero, significa que
o decodificador interpretará ausência de erro,
enquanto o erro de fato existe, pois pelo menos
um dos 15 bits da sequência original é diferente
de zero. São, portanto, os casos em que se tem
interesse. Esses cálculos foram realizados
usando computador, tendo sido analisados os
casos de dois polinômios, 1 ⊕ ∆6 ⊕ ∆7 e 1 ⊕ ∆3 ⊕
∆7, conforme Figura 6, que mostra a
probabilidade condicional para cada uma das
distâncias de erro. A linha pontilhada
corresponde ao código com polinômio 1 ⊕ ∆3 ⊕
∆7. É possível constatar que as distribuições de
que se aproxima de 2-d quando m cresce.
54
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
0,02000
Prob (não detecta/caso há)
erros)
0,01600
0,01200
0,00800
0,00400
0,00000
0
5
10
15
20
Número de bits
Figura 6 Probabilidade condicional de não detecção em função do número de erros
probabilidades são levemente diferentes entre
esses dois polinômios.
Pode ser constatado que não há erros simples
(distância 1) não detectados. Também não há
erros duplos não detectados, pois m = 22 < 2d -1
= 127. De um total de 4.194.303 erros possíveis,
32.767 não são detectados.
Para valores entre 6 e 18 erros por mensagens,
essas probabilidades se aproximam bastante de
2-7 @ 0,008. Como pode ser visto, o pior dos
casos é aproximadamente o dobro desse valor.
Os códigos descrambler-scrambler podem ser
classificados como códigos lineares polinomiais
que se aplicam a mensagens originais, de
tamanho que pode ser fixo ou variável.
Consequentemente, o tamanho das palavras
código, ou seja, das palavras resultantes da
codificação, pode ser fixo ou variável. Esses
códigos apresentam distância mínima de
Hamming igual a 2 entre todas as palavrascódigo, significando que é possível detectar
todos os erros simples. Se as mensagens
originais são mantidas com tamanho menor que
2d-1, a distância mínima é igual a 3, significando
que é possível detectar todos os erros duplos.
Um diferencial significativo desse código é que,
mesmo nos casos em que o erro é mascarado,
partes da mensagem propriamente dita (trecho
de “b” bits) são substancialmente alteradas, pois
são somadas a sequências MLS. Isso significa
que verificações de consistência realizadas em
camadas mais altas do controle da comunicação
poderão, com uma probabilidade muito maior,
detectar inconsistências e, portanto, invalidar
essa mensagem. Esse recurso também é
utilizado nos equipamentos Trópico e Vectura.
2
Correção de erros baseada no código
descrambler-scrambler
O uso do código descrambler-scrambler como
corretor de erros é baseado na capacidade de as
sequências MLS poderem ser reconstituídas
exatamente tanto “para trás” quanto “para frente”,
a partir de qualquer palavra de "d" bits seguidos
da sequência (“d” sendo o grau do polinômio
gerador).
A análise do código como corretor se baseia
também nas propriedades de linearidade das
máquinas de estado implementadas por shiftregisters realimentados e, principalmente, na
separação linear de sequências.
A correção de erros usa como base o processo
de detecção. Além de identificar se a palavra
recebida é diferente da palavra-padrão (todos os
bits iguais a 1), o decodificador também detecta
qual é exatamente a palavra de erro.
Suponha que se utilize um código com d = 7 e
que uma mensagem recebida em SBE tenha em
seus últimos “d” bits uma palavra de verificação
igual a 1011001.
No caso de ausência de erros, essa sequência
deveria ser 1111111. Ou seja, a palavra de erro é
0100110, que possui bits “1” nas posições com
erro.
Faz-se inicialmente a análise para erro simples,
conforme Figura 7, ou seja, considerando-se que
o sinal SER teve um único bit “1” em sua
mensagem, que provocou um único bit errado no
sinal STE. Consequentemente, no instante de
ocorrência desse pulso, e em uma análise de
separação linear, o shift-register ao carregar
esse bit “1” passa para o estado 1000000 e a
partir daí passa a gerar a sequência MLS relativa
ao sinal SER.
Com base na palavra de erro de 7 bits extraída
no fim da transmissão, é possível não somente
reconstruir a sequência SER “para trás” como
também identificar exatamente o ponto em que o
erro ocorreu.
Se fosse um código CRC, em que os primeiros
“b” bits transportam a mensagem original sem
alteração, com base nessa palavra de erro, seria
possível identificar o instante de erro e corrigir
exatamente o bit correspondente na mensagem
recebida.
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
55
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
No código descrambler-scrambler, como os bits
da mensagem original também são alterados
pelo erro, não somente o bit correspondente ao
instante de erro deve ser corrigido, como todos
os bits a partir dele. Ou seja, é preciso voltar ao
sinal SBE, “limpando” todo o trecho de bits
errados entre o fim da mensagem e o instante do
erro, conforme Figura 7, que mostra o conceito
de “espelho” próprio desse novo código corretor.
A partir do instante de detecção do erro, os sinais
SER e SBE passam a ser tratados “em espelho”,
ou seja, de trás para frente, e o sinal SBE é limpo
até o ponto de erro relativo ao estado 0000001
no shift-register. Para isso, cada mensagem SBE
precisa ser armazenada na recepção até que
esse tratamento seja realizado.
Nesse ponto, lançou-se mão de mais uma
propriedade interessante das sequências MLS.
Se o shift-register com realimentações dadas por
um polinômio gera uma sequência MLS, um
shift-register com as realimentações dadas por
um “polinômio simétrico” gera a sequência ao
contrário, ou seja, de “trás para frente”, como
desejado. Esse recurso tem algumas aplicações
práticas (XIANG et al., 2003).
Exemplificando, se o shift-register com
realimentações dadas pelo polinômio x0 + x3 + x7
gera uma sequência MLS, o shift-register com
realimentações x (7-0) + x (7-3) + x (7-7) = x0 + x4 +
x7 gera a sequência espelho.
Uma propriedade extremamente interessante
desse código corretor é que, assim como o
código detector, ele pode ser usado para
mensagens de tamanho variável.
Uma condição para o funcionamento desse
código corretor é a de que o tamanho máximo
das mensagens transmitidas, incluindo a palavrapadrão de verificação de "d" bits inserida no fim
da mensagem, seja menor do que 2d -1, ou seja,
menor do que o período da sequência MLS
correspondente. De fato, se essa condição não
fosse atendida, poderia haver ambiguidade na
identificação do ponto em que ocorreu o erro.
A decodificação que utiliza um “gerador de MLS
espelho” apresenta as seguintes características:
• A mensagem recebida em SBE deve ser
carregada inteira em um buffer ou memória.
• Identifica a palavra de erro.
• Carrega essa palavra de erro de forma
invertida no gerador de MLS espelho.
• Gera a MLS espelho, correspondente ao sinal
SER espelho, a partir desse gerador, até
encontrar a palavra de "d" bits correspondente
a um bit “1” mais “d-1” bits zero. Nesse ponto
é interrompido o processo de correção.
Período m
d
SE
MLS
SER
1000000
0100110
Espelho
trecho de trecho
SBE que
precisa
ser limpo
de SBE
que precisa
ser
SBE
li
d
MLS espelho (de limpeza)
SER espelho
SBE espelho
0000001
0110010
100110
1001101
1
trecho
SBEespelha
ser
trecho
de SBE espelho
a ser limpo
d
li
d
SB espelho
“fim”
“fim”da
da mensagem
mensagem espelho
lh
“inicio”
da mensagem
“início” da
mensagem
espelho
lh
Figura 7 Processo de limpeza em espelho
56
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
•
Enquanto tal ponto não for encontrado, a
sequência SBE deverá ser somada em “ouexclusivo”, bit a bit, de trás para frente, com a
sequência SER espelho.
A Figura 8 oferece um exemplo de
implementação do código corretor.
SA = 011100 1111
ST = 010011 0100
Representa
o
erro no 3 bit
SE = 001000 000
Canal de Transmissão
SR = STE = 011011 0100
Scrambler (Decodificador)
1010
SBE = 010011 1010
1010
No início do
espelhamento
SRE espelho =
1010 11100
SBE espelho = 0101 110010
Corrige
até aqui
SB espelho =
1111 001110
SB 011100 1111
Figura 8 Implementação de código corretor de
erros
Considere uma mensagem com b = 6 bits e d = 4
bits de palavra-padrão de verificação, totalizando
m = 10 bits de mensagem e com o polinômio
primitivo correspondente igual a 1+x1+x4.
Considere ainda, shift-register de codificação
(descrambler) e de decodificação (scrambler),
ambos com conteúdo inicial 0000. Considere
uma mensagem original transmitida igual a
011100, sendo acrescido 1111 nos quatro
últimos bits correspondentes à palavra-padrão de
verificação. De acordo com o polinômio gerador,
é gerada no descrambler a mensagem 010011
0100 no sinal ST. Suponha-se que o sinal SE
apresente um erro, ou seja, um bit “1” no terceiro
intervalo de bit, significando que o terceiro bit de
ST é invertido, teremos, em função do polinômio
gerador, que STE = 011011 0100. No scrambler
do decodificador é gerada em correspondência a
mensagem SBE = 010011 1010. A partir do
terceiro bit dessa mensagem os bits são
somados com a sequência SER. Até esse ponto,
a sequência SER não é conhecida.
Na recepção, um shift-register espelho gera a
mensagem SER espelho. Para isso, a palavra de
erro resultante do “ou-exclusivo” dos últimos 4
bits de SBE com a palavra-padrão 1111 é
carregada no registro espelho, mas invertida,
pois deve-se gerar a sequência para trás (1010).
O
shift-register
espelho
tem
como
realimentações o polinômio simétrico 1+x3+x4 e,
portanto, gera a MLS para trás, correspondendo
ao espelho de SER: 1010 111100. Quando o
padrão 100 é detectado em SER espelho
significa que foi encontrado o ponto de erro, que
corresponde ao oitavo bit (ou terceiro de frente
para trás). Até esse oitavo bit a sequência SER
espelho é somada com a sequência SBE
espelho, gerando a sequência SB espelho 1111
001110. A partir do oitavo bit, a sequência SB
espelho é mantida igual a SBE espelho.
Finalmente SBE espelho é “desinvertida” e os
bits 1111 de verificação são retirados, resultando
na sequência original 011100.
Erros múltiplos, com mais de um erro por
mensagem podem, com probabilidade dada pelo
código detector, ser detectados, mas não podem
ser corrigidos. De fato, numa análise de
separação linear semelhante à realizada para o
detector de erros, cada um dos dois ou mais
pulsos de SE desencadeia em SER uma
sequência MLS iniciada na palavra de “d-1” bits
“0” seguidos de um bit “1” no registrador do
decodificador (scrambler). A sequência resultante
da soma dessas MLS, conforme visto
anteriormente, é a própria MLS deslocada de
outro valor. Quando essa MLS atinge o final da
mensagem, o registrador apresentará uma
palavra a partir da qual não se consegue
reconstituir a SER espelho.
No caso de erros múltiplos, há situações em que
o erro pode ser detectado e outras em que o erro
não é detectado.
Nos casos em que o erro múltiplo não é
detectado no código detector, o erro também não
será detectado no código corretor pois a palavra
de verificação não é alterada. Cabe em seguida
analisar a probabilidade de, havendo alteração
na palavra de verificação, essa palavra ser
corrigida erroneamente, ou seja, não detectada.
Isso ocorre quando o decodificador faz o
processo de limpeza pensando que está
corrigindo um erro simples, mas essa correção
está errada.
O erro múltiplo será detectado como tal e,
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
57
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
portanto, não será corrigido, quando, a partir da
palavra de erro no registrador é gerada a SER
espelho e não se encontra a palavra “1” seguida
de “d-1” zeros até o fim da mensagem em SEB
espelho.
De acordo com a análise feita com base na
Figura 1, a MLS resultante da soma de mais de
um pulso de erro tem uma fase distribuída de
forma pseudoaleatória. Isso significa que o ponto
de marcação de erro correspondente a palavra
de um bit “1” seguida de “d-1” bits “0” pode se
encontrar a uma distância (em períodos de bit)
entre “1” e “2d -1” períodos. Quando essa
distância é maior do que m, essa palavra não é
encontrada e a condição de erro pode ser
deduzida. Podemos concluir que a probabilidade
de não detecção deve ser aproximadamente de
b/2d.
Suponha, por exemplo, que b = 1.024 e d = 16,
ou seja, 2d = 65.536. Nesse caso a probabilidade
de não detecção de erros múltiplos seria de
aproximadamente 1.024 / 65.536 = 1 / 64.
A probabilidade de não detecção pode ser
diminuída aumentando o tamanho da palavra de
verificação. No mesmo caso, por exemplo, para
b = 1.024 e d = 32, a probabilidade de não
detecção seria aproximadamente 1.024 /
4.294.967.296 = 2,38 x 10-7.
Outra opção ao processo de espelhamento para
implementar esse código é usar uma tabela que,
a partir da palavra de erro detectada, indique em
que posição ocorreu o erro. A palavra extraída do
registrador de deslocamento (scrambler) pode
ser usada como endereço dessa tabela (por
exemplo, uma memória ROM) que fornecerá
exatamente a posição da mensagem m na qual o
erro deve ter ocorrido e a partir da qual a limpeza
da sequência SBE deve ser realizada. A partir
desse ponto, e agora de forma não espelhada, a
sequência SBE deve ser gerada com a MLS a
partir da palavra com “d-1” zeros e “1”. Quando
o ponto indicado pela tabela está a uma distância
maior do que o comprimento da mensagem m, a
condição de erro pode ser identificada.
Outro artifício para realizar mais rapidamente o
processo de limpeza, que poderá ser usado tanto
no caso do espelhamento como no caso do uso
de tabela, é o de conversão do tratamento
(máquinas de estado) de serial para paralelo,
conforme Valenzuela (1994). Nesse caso, a
limpeza pode ser feita, por exemplo, de byte em
byte em vez de bit em bit.
O código corretor de erros descramblerscrambler é um código polinomial de distância
mínima de Hamming igual a 3 entre todas as
palavras-código, pois consegue detectar todos os
erros simples. Assim como no caso do código
detector, um diferencial significativo desse código
é que, mesmo nos casos em que o erro é
mascarado e, portanto, não é corrigido ou é
58
corrigido erroneamente, partes da mensagem
propriamente dita (trecho de “b” bits) são
substancialmente alteradas, pois são somadas
com sequências MLS. Isso significa que
verificações de consistência realizadas em
camadas mais altas do controle da comunicação
poderão, com uma probabilidade muito maior,
detectar inconsistências e, portanto, invalidar
essa mensagem.
3
Caracterização dos códigos descramblerscrambler por meio de grafos-fatores
Os grafos-fatores correspondem a uma técnica
que pode ser usada para representar sistemas
codificados
por
meio
de
modelagens
comportamental e probabilística.
Para aplicar esse método aos códigos
descrambler-scrambler, é construído em primeiro
lugar o grafo-fator do codificador, posteriormente
o do decodificador, e finalmente os dois são
relacionados pelo modelo estatístico do canal de
transmissão. Na mensagem, ou “bloco” de m =
b+d bits, os m bits da mensagem original são
considerados “variáveis”. É utilizado também o
conceito de bits de “controle” que representam as
equações de paridade. No caso dos códigos
descrambler-scrambler, todos os bits da
mensagem transmitida são considerados bits de
controle e não somente os bits de verificação.
Na construção de um grafo, em um dos lados
são colocados os nós de variáveis, habitualmente
representados por círculos e, no outro, são
colocados os nós de controle, ou de paridade,
habitualmente representados por quadrados. O
número de linhas que confluem em um dado nó
chama-se grau do nó e o número total de linhas
do grafo é igual ao número de “1” da matriz de
teste de paridade (ou matriz H – a ser definida)
do código. Cada nó de variável está associado a
um bit de mensagem e cada nó de paridade está
associado a uma equação de paridade. No caso
dos códigos descrambler-scrambler, essas
equações estão relacionadas com os polinômios
das sequências MLS utilizadas.
Para encontrar o modelo de grafo-fator do código
descrambler-scrambler (MACKAY, 2003), utilizase uma matriz m x m, cujas linhas são bases
vetoriais para o código em questão. Essa matriz
é denominada matriz de teste de paridade.
Através de operações elementares “ou-exclusivo”
podemos descobrir a matriz de teste de paridade
do código descrambler-scrambler.
Para ilustrar esse método foi usado um caso
prático, considerando o código descramblerscrambler com configuração de geração do
seguinte polinômio (Figura 8):
ST = SA ⊕ SA. ∆1 ⊕ SA. ∆4
Assim, podemos representar os estados do
registrador, conforme Tabela 1.
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
Tabela 1 Representação de estados do codificador
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
P1
0
B1
B2
B3
B4
B5
B6
B7
B8
B9
P2
0
0
B1
B2
B3
B4
B5
B6
B7
B8
P3
0
0
0
B1
B2
B3
B4
B5
B6
B7
P4
0
0
0
0
B1
B2
B3
B4
B5
B6
ST
B1
B1+B2
B2+B3
B3+B4 B1+B4+ B2+B5+ B3+B6+ B4+B7+ B5+B8+ B6+B9
B5
B6
B7
B8
B9
+B10
Observa-se que o estado inicial do registrador é
0000. O conteúdo do registrador após a
introdução do i-ésimo bit da sequência de
informação no codificador caracteriza o estado
da mensagem ST, em um dado instante.
Sabe-se que os bits de paridade inseridos no
código
descrambler-scrambler
são,
por
convenção, todos iguais a 1. Fazendo ST7, ST8,
ST9 e ST10 igual a 1, pode-se simplificar o
resultado obtido.
Assim, das expressões da última linha da Tabela
1 pode-se escrever:
ST1 = B1
ST2 = B1+B2
ST3 = B2+B3
ST4 = B3+B4
ST5 = B1+B4+B5
ST6 = B2+B5+B6
ST7 = B3+B6+B7
ST8 = B4
ST9 = B5
ST10 = B6
Apesar de B7 ser igual a 1, em ST7 ele se
mantém na equação porque não se cancela.
Dessa forma, tem-se a matriz HC de teste de
paridade do codificador da Figura 9.
A matriz encontrada é de “baixa densidade”, isto
é, a matriz apresenta mais ocorrências de “0” do
que de “1”, o que é interessante, pois implica um
algoritmo menos complexo.
Observa-se que a análise para detecção de erro
do código descrambler-scrambler não se resume
apenas aos 4 últimos bits da palavra e toda a
palavra-código é modificada.
Dessa forma, o grafo-fator associado ao código
descrambler-scrambler deverá ser a
representação de toda a palavra-código,
conforme Figura 10, que representa o lado do
codificador em que se tem 10 bits de variáveis e
10 bits de controle.
Figura 9 Matriz de teste de paridade do codificador
Figura 10 Fator de grafo do codificador
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
59
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
Tabela 2 Representação de estados do codificador
R1
R2
R3
R4
R5
R6
P1
0
R1
R1+R2
R1+R2+R3
R1+R2+R R2+R3+R R1+R3+R
3+R4
4+R5
4+R5+R6
R2+R4+R
5+R6+R7
R1+R3+R5+ R1+R2+R4+R6
R6+R7+R8
+R7+R8+R9
P2
0
0
R1
R1+R2
R1+R2+R R1+R2+R R2+R3+R
3
3+R4
4+R5
R1+R3+R
4+R5+R6
R2+R4+R5+ R1+R3+R5+R6
R6+R7
+R7+R8
P3
0
0
0
R1
R1+R2
R1+R2+R R1+R2+R
3
3+R4
R2+R3+R
4+R5
R1+R3+R4+ R2+R4+R5+R6
R5+R6
+R7
P4
0
0
0
0
R1
R1+R2+R
3
R1+R2+R
3+R4
R2+R3+R4+ R1+R3+R4+R5
R5
+R6
SB
R1
R1+R2
R1+R2+R3
R1+R2+R3+ R2+R3+R R1+R3+R R2+R4+R
R4
4+R5
4+R5+R6 5+R6+R7
R1+R3+R
5+R6+R7
+R8
R1+R2+R4+
R2+R3+R5+R7
R6+R7+R8+
+R8+R9+R10
R9
R1+R2
Os nós de variáveis estão conectados aos nós
de teste de paridade de controle se o elemento
(i,j) da matriz H for igual a 1. Esses nós de
controle são representados por quadrados e
correspondem às operações “ou-exclusivo”, de
acordo com o polinômio da sequência MLS
usada no código.
Da mesma forma que o codificador, o
decodificador do código descrambler-scrambler
pode ser representado como um grafo bipartido.
Seguindo o mesmo procedimento e assumindo
um registrador com a mesma configuração do
R7
R8
R9
R10
registrador do codificador, a Tabela 2 mostra as
relações envolvidas.
A última linha representa as relações entre os
bits de controle e os de variáveis (entrada do
decodificador). Tem-se, na Figura 11, a matriz
HD de teste de paridade do decodificador.
A Figura 12 ilustra o grafo-fator do decodificador.
É bem mais complexo do que o do codificador
devido à maior quantidade de “1” na matriz HD.
O método dos grafos-fatores pode ser usado
para analisar o comportamento estatístico dos
códigos. Análises de probabilidade de não
detecção ou não correção podem ser realizadas.
Figura 11 Matriz de teste de paridade do decodificador
Figura 12 Fator de grafo do decodificador
60
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
O meio de transmissão, por exemplo, o canal de
sinalização da Plataforma Trópico ou Vectura,
pode ser caracterizado como um processo
estocástico, ao qual são associados:
• um alfabeto de entrada A = {a1, a2, a3,....,
an};
• um alfabeto de saída B = {b1, b2, b3,...., bn};
• uma distribuição de probabilidade P (A/B),
que relaciona os símbolos que saem do canal
em função dos símbolos que entram.
Pode-se classificar o canal como do tipo sem
memória, considerando que a distribuição de
probabilidades atribuídas para esse canal é
independente do histórico de símbolos
transmitidos, ou seja, as probabilidades
atribuídas ao canal, p (bj/ai), i=1,2,..n e j=1,2,...n,
são independentes dos símbolos anteriores e
posteriores transmitidos. Um canal simples, cujo
modelo é largamente empregado, é o canal
binário simétrico, descrito pelo diagrama abaixo.
Considerando a probabilidade de um símbolo da
entrada (0 ou 1) ser transmitido sem erro para a
saída e “1-s” é a probabilidade de o símbolo ser
transmitido com erro tem-se: p (0/0) =p (1/1) =s e
p (0/1) =p (1/0) =1-s.
Sendo um produto de fatores, essa probabilidade
condicional conjunta também poderá ser
representada por um grafo-fator e cada nó de
paridade representa a função probabilidade
condicional a priori p (bj/ai). Se os valores b
recebidos na saída do canal não são, de fato,
variáveis, mas sim constantes, cada nó de
paridade desse grafo apenas depende de uma
única variável ai. Dessa forma, podemos
representar o canal de sinalização de acordo
com a Figura 13, na qual cada relação de bit de
entrada para bit de saída tem associada uma
probabilidade P (b/a).
Agrupando o grafo-fator do codificador e do
decodificador em série com o fator de grafo do
canal binário simétrico e sem memória, obtém-se
o grafo-fator global do código descramblerscrambler da Figura 14.
Dessa forma, conforme proposto inicialmente, foi
exemplificado como pode ser obtido o modelo
global baseado em grafo do código descramblerscrambler. Em um trabalho futuro, poderá ser
avaliada a viabilidade do uso desse modelo na
análise probabilística da eficiência do código em
questão.
Conclusão e trabalhos futuros
Foram apresentados neste artigo o código
detector de erros descrambler-scrambler, sua
utilização
na
comunicação
interna
de
equipamentos Vectura e sua evolução para
código corretor de erros. Foi apresentado
também como esse código pode ser modelado
usando análise de grafos-fatores.
P(bi/ai)
ai
Figura 13 Fator de grafo do canal
Codificador
Canal
Decodificador
Figura 14 Fator de grafo global do código descrambler-scrambler
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009
61
Código descrambler-scrambler detector e corretor de erros e seu uso em equipamentos Vectura
A grande simplicidade de implementação e a
possibilidade de ser usado em sistemas de
transmissão que envolvem mensagens de
diferentes
comprimentos
motivaram
o
desenvolvimento
desse
código
nos
equipamentos Trópico e Vectura, que incluem
centrais telefônicas, softswitches usados em
redes NGN e pontos de transferência e
tratamento de sinalização "intrusivos". Apesar de
serem projetados para não apresentar erros de
transmissão, esses equipamentos podem ser
submetidos a condições bastante adversas em
termos de ruídos elétricos, que podem levar a
probabilidades não nulas de erros de
transmissão. O uso comercial de equipamentos
com o recurso de detecção de erros tem se
mostrado eficiente nesses casos. Além disso, é
apresentado um código corretor de erros que,
baseado na mesma topologia descramblerscrambler, também pode ser usado em sistemas
com diferentes comprimentos de mensagens.
São destacadas características que diferenciam
esses códigos.
Como próximo passo, essa modelagem poderá
ser usada para fazer uma melhor avaliação do
desempenho desse código. Também poderá
realizar as implementações sugeridas de tabela
de identificação do ponto de ocorrência do erro
em função da palavra final de erro e de
aceleração do processo de decodificação usando
paralelização de máquinas de estado, como
sugerido em Valenzuela (1994).
Agradecimentos
A elaboração deste artigo foi feita dentro do
Projeto CONVERTE, realizado com apoio da
FINEP e recursos do FUNTTEL. Os autores
registram aqui seu reconhecimento a todos
aqueles envolvidos na viabilização deste projeto
e agradecem particularmente as revisões
realizadas por Angelo Antônio Mantovani e
Edson Porto Fassoni.
Referências
GOLOMB, S. W. Shift Register Sequences,
Editora Holden-Day, 1967.
MACKAY, D. J. C. Information Theory,
Inference, and Learning Algorithms Cambridge University Press 2003.
PETERSON, W.; WELDON E.
Correcting Codes, MIT Press, 1961.
J.
Error
VALENZUELA, V. Error Detecting code for a
Digital Transmission System Based on a
descrambler-scrambler
Configuration
–
Campinas, 1987, International Symposium on
Information and Coding Theory.
VALENZUELA, V. Serial to Parallel Conversion
of State Machines using Multi-Jump FlipFlops, Rio de Janeiro, 1994 International
Telecommunications Symposium.
XIANG, N. et al. Time-reversal maximum-length
sequence pairs for simultaneous acoustical dual
source measurements. Acoustical Society of
America Journal, Vol. 113, Issue 4, April 2003.
ZUFFO, J. A. Subsistemas Digitais e Circuitos
de Pulso, Editora USP, 1974.
Abstract
This article describes a new error correcting code based on a descrambler-scrambler structure. It
describes also its modeling in terms of factor graphs. This code corresponds to an evolution of the
descrambler-scrambler error detecting code previously developed for the Vectura equipment. For this
purpose the basic concepts are initially described as well as the motivation of these codes, particularly in
the Vectura equipment internal processor network. Furthermore, the error detecting code utilized in such
network and a new error correcting code are described. Finally, an analysis is made of the use of factor
graphs to model such code. With the presentation of the error detection and error correction codes, their
efficiency is analyzed using an approach based on the characteristics of the maximum length pseudo
random sequences.
Key words: Error detecting code. Error correcting error. Factor graphs. Descrambler-scrambler.
62
Cad. CPqD Tecnologia, Campinas, v. 5, n. 1, p. 49-62, jan./jun. 2009