Descodificação iterativa de códigos LDPC por transferência de mensagens em grafos de factores

1 Descodificação iterativa de códigos LDPC por transferência de mensagens em grafos de factores © Sílvio A. Abrantes Departamento de Engenharia Electrotécnica e de Computadores Faculdade de Engenharia, Universidade do Porto Porto, Portugal [email protected] Julho de 2005 Resumo: Os códigos turbo e LDPC, os melhores códigos correctores de erros da actualidade, partilham em comum o facto de usarem métodos de descodificação iterativa que recorrem a algoritmos de natureza idêntica. Em particular os códigos LDPC são habitualmente caracterizados por grafos bipartidos de Tanner e grafos de factores e são descodificados com um algoritmo muito genérico de transferência de mensagens entre nós dos grafos, o algoritmo da soma-e-produto, de que o algoritmo BCJR, usado nos turbo-códigos, é um caso particular. Neste tutorial é apresentado o algoritmo da soma-e-produto e duas simplificações (os algoritmos “max-product” e “min-sum”) e a sua utilização é ilustrada através de vários exemplos detalhados. Palavras-chave: códigos LDPC, algoritmo da soma-e-produto, algoritmos de transferência de mensagens, códigos em grafos, grafos de Tanner, grafos de factores. 1. Objectivo Este texto é um tutorial de apresentação da descodificação iterativa por transferência de mensagens em grafos de Tanner, método normalmente usado na descodificação de códigos LDPC. São abordados os algoritmos da soma-e-produto, “max-product” e “min-sum” e a exposição serve-se de exemplos numéricos para ilustrar os procedimentos. O texto destina-se a todos os que desejem compreender o funcionamento dos algoritmos que, através de grafos, descodificam códigos correctores de erros de uma forma iterativa muito eficiente. A estrutura do tutorial é a seguinte: na Secção 2 é feita a introdução do tema, o que inclui referências não só aos códigos LDPC mas também aos grafos de Tanner e de factores; na Secção 3 é explicado o funcionamento dos algoritmos de transferência de mensagens em grafos de factores, mostrando-se como se calculam as mensagens com o algoritmo da soma-e-produto, assumam aquelas o papel de estimativas de probabilidades condicionais ou sejam logaritmos de razões de verosimilhanças (LLR); os algoritmos de cálculo aproximado “max-product” e “min-sum” são também expostos na Secção 3; a Secção 4 apresenta um exemplo numérico detalhado de descodificação iterativa de um código de blocos através do algoritmo da soma-e-produto; o tutorial prossegue com um Apêndice e termina com a lista de referências. 2. Introdução aos códigos LDPC e aos grafos de Tanner A Fig. 1 apresenta o diagrama de blocos de um sistema genérico de codificação e descodificação de canal. Seja u = u1u2…uk uma sequência de k bits que, aplicada a um codificador binário de taxa k/n, produz a palavra de código x = x1x2…xn. Esta, depois de atravessar o canal de comunicações, é transformada na sequência y = y1y2…yn recebida 2 pelo descodificador. É tarefa deste estimar convenientemente a palavra de código x ou a sequência binária original, u. Canal Descodificador Codificador x = x1x2…xn u = u1u2…uk y = y1y2…yn û Fig. 1 Diagrama de blocos de um sistema genérico de codificação/descodificação. Neste texto vamos ver como descodificar a sequência y quando usamos códigos LDPC. Em particular, vamos ver como o fazer usando grafos bipartidos, ou de Tanner. Antes de começar, contudo, temos de saber o que são códigos LDPC, grafos de Tanner e… LLR a posteriori. 2.1. Breve introdução aos códigos LDPC Os códigos LDPC (de “Low Density Parity Check”) foram inventados por Robert Gallager, que os apresentou pela primeira vez em 1962 [1] e depois na sua tese de doutoramento em 1963 [2]. Apesar de Gallager também ter proposto o método (iterativo) de descodificação, a verdade é que os códigos LDPC eram demasiado “avançados” para a tecnologia da época e ficaram adormecidos e deixados ao abandono durante cerca de trinta anos. A letargia terminaria em 1993 com o aparecimento dos seus despertadores, os turbo-códigos [3]. Um código LDPC é um código de blocos binário caracterizado por uma matriz de verificação de paridade H esparsa, isto é, uma matriz em que o número de “uns” é pequeno em relação ao número de “zeros”. Isso quer dizer que o número de variáveis envolvidas em cada equação de paridade é pequeno. Na verdade, como as linhas de H representam as equações de paridade e as colunas representam os bits da palavra de código, o elemento da linha j e coluna i só é 1 se o bit xi fizer parte da j-ésima equação de paridade. A Fig. 2 apresenta um exemplo de matriz H de um código LDPC em que existem seis bits 1 em cada linha e três bits 1 em cada coluna. A um código em que, como neste, o número de “uns” por coluna ou por linha é constante chama-se código LDPC regular, caso contrário diz-se… irregular! Actualmente os códigos LDPC são, juntamente com os códigos turbo, os códigos correctores de erros com melhor desempenho (em particular os códigos LDPC irregulares) porque são os que melhor se aproximam do inultrapassável limite de Shannon. Na prática os códigos LDPC têm comprimentos muito longos, com valores de n da ordem das dezenas de milhar ou mesmo mais (um milhão, por exemplo!). É usual descrever os códigos LDPC através de grafos de Tanner. 3 00100010100001010010 01001010010010000100 10000100010000100110 01000001001100010001 10010001001001001000 00110010100010000001 00001101010100100000 10000000001100001110 01010000100011000001 001011000000001110 =H 00 ⎡⎤ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎢⎥ ⎣⎦ Seis bits “1” por linha Três bits “1” por coluna Código LDPC (3, 6) Fig. 2 Exemplo de matriz H de um código LDPC regular. 2.2. Grafos de Tanner e grafos de factores Os grafos de Tanner são devidos a R. Michael Tanner, que os inventou em 1981 para caracterizar e descodificar códigos correctores de erros como BCH e LDPC [4]. Os grafos de Tanner são grafos bipartidos. Com isto quer-se dizer que o grafo está dividido em duas regiões distintas, cada uma com seu tipo de nó, ligadas por linhas que unem nós de tipo diferente. Supondo que queremos representar um código de blocos (n,k), num dos lados do grafo são colocados n nós de variáveis, habitualmente representados por círculos, e no outro são colocados n – k nós de controlo, ou de paridade, habitualmente representados por quadrados (veja-se a Fig. 3). Ao número de linhas que confluem num dado nó chama-se grau do nó e o número total de linhas do grafo é igual ao número de “uns” da matriz H do código. Nos grafos de Tanner cada nó de variável está associado a um bit de código e cada nó de paridade está associado a uma equação de paridade (e como tal, apenas está ligado às variáveis dessa equação). Sendo assim, podemos encarar cada nó de paridade como uma função com dois valores possíveis: se a equação de paridade respectiva for satisfeita vale 1, se não o for vale 0. Consideremos então um código linear binário de Hamming (n, k) = (7, 4) com a matriz de verificação de paridade H da Fig. 3, para a qual as equações de paridade são 1235 2346 3457 0 0 0 xxxx xxxx xxxx ⊕ ⊕⊕= ⊕ ⊕⊕= ⊕ ⊕⊕= sendo x = x1, x2,…, x7 uma palavra de código. A mesma Fig. 3 mostra o correspondente grafo de Tanner. Neste exemplo temos três funções de quatro variáveis1, ),,,( 53211 xxxxf , ),,,( 64322 xxxxf e ),,,( 75433 xxxxf , funções que, como se acabou de dizer, valem 1 ou 0 consoante as 1 Usando a terminologia dos grafos bipartidos: os nós de paridade têm todos grau 4. Já os nós de variáveis têm graus diversos: por exemplo, a variável x3 tem grau 3 e a variável x4 tem grau 2. 4 equações de paridade do código são ou não satisfeitas, ou seja, f1, f2 e f3 são funções binárias indicadoras de pertença ao código. Portanto, uma dada palavra de n bits pertence ao código se todas as funções indicadoras forem iguais a 1 e não pertence se pelo menos uma das funções for nula. A sequência 1101000, por exemplo, não é uma palavra de código pois nem todas as funções associadas aos nós de paridade valem 1: 1 2 3 110 0 0 1 1010 0 1 01001 0 f f f + ++= ⇒ = + ++ = ⇒ = + ++= ⇒ = x1 x2 x3 x4 x5 x6 x7 + + + f1 f2 f3 ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = 1011100 0101110 0010111 H Fig. 3 A matriz de paridade de um código de Hamming (7,4) e o grafo de Tanner associado. Poderemos escrever então: ⎩ ⎨ ⎧ ≠⊕⊕⊕ =⊕⊕⊕ =⊕⊕⊕= 00 01 )(),,,( 5321 5321 532153211 xxxx xxxx xxxxxxxxf δ (1) )(),,,( 643264322 xxxxxxxxf ⊕⊕⊕= δ (2) )(),,,( 754375433 xxxxxxxxf ⊕⊕⊕= δ (3) Nas expressões atrás δ(x) representa o delta de Kronecker, 10 () 00 x xx δ = ⎧ =⎨≠ ⎩. Na aplicação que nos interessa, a descodificação, os grafos de Tanner são usados para transferir mensagens entre nós através das linhas que os unem. Ora é bem de ver que quanto mais linhas o grafo possuir mais mensagens são transferidas e mais cálculos são necessários. Aqui está a razão pela qual os códigos LDPC, com o seu número reduzido de “uns” em H, estão particularmente bem talhados para a descodificação baseada em grafos bipartidos. 2.2.1. Dos grafos de Tanner aos grafos de factores Embora de modo breve, é conveniente fazer uma referência aos grafos de factores. Suponhamos que uma dada função, dita função global, é igual ao produto de funções locais de várias variáveis, como 1234 1132143234 (, , , ) (, )(, )(, , ) g xxxx hxxhxxhxxx = . Um grafo de factores é um grafo bipartido que serve para visualizar a factorização da função 5 global indicando que variáveis são argumentos de que funções locais. Um exemplo, referente à função 1234 (, , , ) g xxxx , é apresentado na Fig. 4. Do ponto de vista dos grafos de factores o grafo de Tanner do código de Hamming da Fig. 3 representa o produto das três funções indicadoras f1, f2 e f3, 112352234633457 (,,,)(,,,)(,,,) f xxxxfxxxxfxxxx, de valor 1 ou 0 consoante a sequência de sete bits x = x1, x2,…, x7 pertença ou não ao código. x1 x2 x3 x4 h1 h2 h3 Fig. 4 O grafo de factores de 1234 1132143234 (, , , ) (, )(, )(, , ) g xxxx hxxhxxhxxx=. Cronologicamente primeiro surgiram os grafos bipartidos de Tanner. Depois, por volta de 1996, Wiberg e outros modificaram-nos por forma a conterem variáveis de estado [5] [6] [7]. Mais tarde ainda surgiram os grafos de factores [8] [9], generalizações dos grafos “tipo” Wiberg que se aplicam a funções factorizáveis como a de cima. O algoritmo genérico de cálculo em todos esses grafos é denominado algoritmo da soma-e-produto e vai ocupar-nos bastante em breve. Exemplo 1 Os grafos de factores prestam-se a composições gráficas interessantes. Voltemos ao código de Hamming (7,4) da Fig. 3. O seu grafo de Tanner desenhado como grafo de factores apresenta uma atraente simetria: x 1 x 2 x 3 x 4 f 3 x 5 x 7 x 6 f 2 f 1 6 2.2.2. Grafo de factores associado a um canal binário simétrico Na Fig. 5 é apresentado o diagrama de probabilidades de transição de um canal binário simétrico sem memória (ou canal BSC2) com probabilidade de erro p, ou seja, com 1 (|) p yx pyx p yx −= ⎧ =⎨≠ ⎩ ou, equivalentemente, (1 )(1 ) 0 (|) (1 ) (1 ) 1 py p y x pyx py pyx + −− = ⎧ =⎨ − +− = ⎩. Suponhamos que a palavra de código x = x1, x2,…, xn é transmitida através do canal, que a transforma na sequência binária y = y1, y2,…, yn. x P(y|x)y 0 1 0 1 1-p 1-p p p Fig. 5 Um canal binário simétrico com probabilidade de erro p. Como o canal BSC não tem memória as n transmissões de símbolos são independentes e portanto a probabilidade condicional conjunta a priori p(y|x) é igual ao produto das probabilidades condicionais individuais p(yi|xi): 12 12 1 (|) (, , , | , , , ) ( | ) n nnii i p py y y x x x py x = == ∏ yx …… . Sendo um produto de factores esta probabilidade condicional conjunta pode ser representada por um grafo de factores em que cada nó de paridade representa a função probabilidade condicional a priori p(yi|xi). Ora, atendendo a que os valores yi recebidos à saída do canal não são, de facto, variáveis mas sim constantes cada nó de paridade desse grafo apenas depende de uma única variável, xi. Com n = 7 o grafo de factores do canal BSC é o apresentado na Fig. 6. p(y 1 |x 1 ) x 1 x 2 x 3 x 4 x 5 x 6 x 7 p(y 2 |x 2 ) p(y 3 |x 3 ) p(y 4 |x 4 ) p(y 5 |x 5 ) p(y 6 |x 6 ) p(y 7 |x 7 ) Fig. 6 O grafo de factores de 7 1 (|) ( | ) ii i p py x = =∏ yx . 2.2.3. Grafo de factores associado a um canal AWGN O grafo de factores de um canal afectado de ruído gaussiano branco aditivo – o conhecido canal AWGN3 – é semelhante ao grafo de factores de um canal BSC. Tal 2 BSC: “Binary Symmetric Channel” 7 como este, o canal AWGN não tem memória e a probabilidade condicional a priori de uma dada sequência é igual ao produto das probabilidades condicionais individuais. Mas agora as probabilidades discretas dão lugar à função densidade de probabilidade (fdp) do ruído gaussiano, de média nula e variância σ2, 22 2 2 1 () 2 y fy e σ πσ − = isto é, N(0,σ2), e a sequência binária de valores lógicos 0 e 1 é convertida na sequência antipodal xi = ±1. Assim, com ruído gaussiano cada um destes valores, -1 e +1, fica associado a uma fdp gaussiana com a mesma variância σ2 e de média -1 e +1, respectivamente (designemo-las por f-(y) e f+(y), como se mostra na Fig. 7). Se na saída do canal recebermos a sequência de valores reais yi as probabilidades condicionais de que precisamos são calculadas para os dois valores possíveis de xi: (| 1) () ii i p yx fy − =− = e ( | 1) ( ) ii i p yx fy + = += . É preciso, contudo, normalizar estes valores para que a sua soma seja unitária, isto é, () 2 () (1) () () 1 1exp2 i ii ii i fy pyx fy fy y σ − −+ = −= = + =+ () 2 () (1) () () 1 1exp 2 i ii ii i fy pyx fy fy y σ + −+ = += = + =+− -1 0 1 y i y f + (y) f - (y) f - (y i ) N (1,σ 2 ) N (-1,σ 2 ) f + (y i ) Fig. 7 As funções densidade de probabilidade gaussianas associadas aos símbolos -1 e +1. Estes valores normalizados desempenham o mesmo papel que os valores de p(yi|xi) do canal binário simétrico, de modo que usaremos p(yi|xi) sem perda de generalidade. 2.2.4. Grafo de factores de um canal BSC em série com um descodificador de canal Juntando os grafos de factores de p(y|x) e do (des)codificador (7, 4) da Fig. 3 obtemos o grafo de factores global4 da Fig. 8. Os nós pi estão “pendurados” e têm apenas um 3 AWGN: “Additive White Gaussian Noise”. 4 No grafo passámos a designar os nós de paridade do canal por pi. 8 vizinho, xi. Dado que o grafo de factores pode ser desenhado como árvore diz-se que os nós pi (ou a linha que une pi a xi) são nós-folha (ou nós-linha). Por vezes os nós pi (os quadrados) são omitidos. x 1 x 2 x 3 x 4 x 5 x 6 x 7 + + + p 1 p 2 p 3 p 4 p 5 p 6 p 7 f 1 f 2 f 3 Canal BSC Descodificador Fig. 8 O grafo de factores global de canal BSC + descodificador. 2.3. Probabilidades e LLR a posteriori É habitual estimar a sequência x a partir da sequência recebida y usando um de dois métodos: estimação de máxima verosimilhança (ou estimação ML, de “Maximum Likelihood”) e estimação da máxima probabilidade a posteriori (ou estimação MAP, de “Maximum A Posteriori”). O primeiro método calcula a probabilidade condicional a priori ( | ) i p xy – para determinar a sequência ˆ x que maximiza (|)pyx – e o segundo calcula a probabilidade condicional a posteriori () (| ) () i ii p x p(x | ) p x p = yy y (também designada por APP5) para determinar o símbolo xi. O método que nos interessa é o método de estimação MAP. Queremos, portanto, calcular a probabilidade de se ter enviado o bit xi dado que se recebeu a sequência y. Além desta probabilidade APP também nos vai interessar usar o logaritmo da razão de probabilidades 1 0 i i p (x | ) p (x | ) = = y y, 1 (|)ln 0 i ii p (x | ) Lx p (x | ) = == y yy, que designaremos por LLR a posteriori6. O critério de decisão final sobre o bit xi é o habitual: se a probabilidade APP ou a razão LLR estiverem acima de um determinado limiar de decisão escolhemos xi = 1, se estiverem abaixo escolhemos xi = 0. O limiar de decisão é 0,5 no caso da APP e 0 no caso da LLR. É costume exprimir o critério desta maneira: 1 0 (|)0 i Lx y≷ 5 APP: “A Posteriori Probability” 6 LLR: “Log-Likelihood Ratio” 9 Portanto, se a LLR for positiva escolhemos o bit 1 e se for negativa escolhemos o bit 0. As probabilidades e as LLR a posteriori podem ser calculadas de diversas maneiras. Em codificação turbo, por exemplo, é normal usar o algoritmo BCJR [10]. Com códigos LDPC é costume recorrer a grafos (de Tanner e de factores) e a algoritmos de transferência de mensagens entre os seus nós. O que contêm as mensagens? Estimativas de probabilidades ou quantidades com elas relacionadas, como a LLR. Vamos ver como se faz. 3. Transferência de mensagens entre nós de grafos Os algoritmos de descodificação baseados em grafos são designados genericamente por algoritmos de transferência de mensagens. O nome que efectivamente tomam depende um pouco do contexto: enquanto que na Teoria da Codificação e na presença de grafos de factores se prefere a designação algoritmo da soma-e-produto (“sum-product algorithm”, ou SP), em redes bayesianas a comunidade da Inteligência Artificial usa mais o termo “belief propagation algorithm” (BP). O que aconteceu é que, por vias e em aplicações muito distintas, ambas as comunidades chegaram a um algoritmo que a outra desconhecia mas que o tempo veio a provar que, afinal, era o mesmo7. O algoritmo BP foi formulado por J. Pearl em 1988 [11] e chama-se assim porque propaga “crenças” (probabilidades) de uns nós de grafos para os outros. Mas já Gallager, mais de vinte anos antes, utilizara um método iterativo semelhante no seu trabalho pioneiro sobre os códigos LDPC. Tanner generalizou-o em 1981 com o algoritmo SP [4]. Mais tarde, já depois do aparecimento dos turbo-códigos em 1993, o algoritmo da soma-e-produto foi aplicado com sucesso aos grafos de factores, do que resultou a sua formulação mais genérica [7]. Na prática, chamemos-lhe nós BP ou SP, estes algoritmos de transferência de mensagens são algoritmos SISO (“Soft Input-Soft Output”) pois a entrada e a saída – probabilidades – são valores reais. Os algoritmos SP e BP são tão gerais que, sem o suspeitarmos, muitos métodos, algoritmos e técnicas conhecidos há décadas não são senão… casos particulares daqueles. A lista é grande e inclui, entre outros, os algoritmos de descodificação de Gallager, Viterbi e BCJR (estes últimos usados em treliças de códigos convolucionais, e não só…) e a descodificação iterativa de turbo-códigos (com o algoritmo BCJR) [12]. E até os filtros de Kalman não escapam [7] [9]. Consideremos então um grafo de Tanner com nós de variáveis xi e nós de controlo fj a trocar mensagens deste género: a variável xi questiona fj sobre as “opiniões” que os outros xi têm dela e fj responde-lhe com as “opiniões” que conhece. Tais perguntas (questões) e respostas reflectem-se na notação que vamos usar: () ij i qx – mensagem do nó de variável xi para o nó de paridade fj () ji i rx – mensagem do nó de paridade fj para o nó de variável xi Estas mensagens, ou probabilidades, são função de um único argumento (a variável xi) quer circulem num sentido quer no outro. A mensagem de xi para fj representa a probabilidade de xi ter um certo valor, dado o valor observado dessa variável (a 7 Porém, Kschischang e outros [7] [8] consideram que o algoritmo BP é um caso particular do “seu” algoritmo SP. 16 r 13 v 3 p 3 + + + f 1 f 3 f 4 r 33 r 43 q 31 v 3 p 3 + + + f 1 f 3 f 4 r 33 r 43 Dos nós de variáveis para os nós de paridade f 2 q 12 v 1 v 2 v 3 v 4 r 22 q 42 q 32 + f 2 q 12 v 1 v 2 v 3 v 4 q 22 q 42 q 32 + Dos nós de paridade para os nós de variáveis Fig. 13 Mensagens entre nós de grafos bipartidos. 22 12 32 42 32 12 42 42 12 32 12 32 42 (1 )(1 ) (1 )(1 ) (1 )(1 )rq q q q q q q q q qqq=− −+− −+− −+ (11) De igual modo o mesmo nó de paridade envia para os nós das variáveis v1, v3 e v4 mensagens com as probabilidades estimadas r21, r23 e r24, respectivamente, as quais se calculam de acordo com 21 22 32 42 1 2 (1 2 )(1 2 )(1 2 )rqqq−=− − − 23 12 22 42 1 2 (1 2 )(1 2 )(1 2 )rqqq−=− − − 24 12 22 32 1 2 (1 2 )(1 2 )(1 2 )rqqq−=− − − 3.1.2. Por que é que é necessário um factor de normalização? Sem normalização as estimativas de probabilidades que as variáveis enviariam aos nós de paridade seriam sempre inferiores às que deles tinham recebido dado estas serem sempre inferiores a um. Por exemplo, se uma variável de grau 4 recebesse os valores 0,6, 0,9 e 0,8 de três nós de paridade a estimativa que iria enviar para o quarto nó seria, sem normalização, igual ao produto 0,6 × 0,9 × 0,8 = 0,432. Suponhamos um caso simples de uma variável x1 de grau 3 que recebe as mensagens r11 e r21 e vai disso informar o nó de paridade 3 enviando-lhe a mensagem 13 13 11 21 qKrr = . Ora deverá também ser 13 13 11 21 1(1)(1)qK r r−= − −. Combinando as duas expressões concluímos que o factor de normalização a usar é 13 11 21 11 21 1 (1 )(1 ) Krr r r =+− − , 17 como já sabíamos e está na Eq. (8). No exemplo precedente a mensagem da variável de grau 4 deveria, portanto, ter valor 0,6 0,9 0,8 0,98 0,6 0,9 0,8 0,4 0,1 0,2 × ×= ××+×× , quantidade que é muito mais razoável que a não normalizada 0,432. Exemplo 4 Mensagens de nós de um dado grau expressas à custa de mensagens de “graus” inferiores As mensagens dos nós de um dado grau podem ser expressas à custa de mensagens de nós de grau inferior. Comecemos pela mensagem de um nó de variável de grau 3 (ver Fig. 14a). Se tiver recebido as mensagens a e b de dois nós de paridade, o nó de variável envia para o terceiro nó de paridade uma mensagem que é função de a e b (e a que chamaremos VAR(a,b)): Grau 3: (,) (1 )(1 ) ab VAR a b ab a b = + −− . q i3 = VAR(a,b) a b f 1 f 2 f 3 x i a) f j r j3 = PAR(a,b) x 1 x 2 x 3 a b b) Fig. 14 As funções VAR e PAR em nós de grau 3. Consideremos agora um nó de variável de grau 4 ao qual chegam as mensagens a, b e c. A mensagem que ele transmite para o quarto nó de paridade é (,,) (1 )(1 )(1 ) abc VARabc abc a b c = + −−− . Dividindo o numerador e o denominador por (1 )(1 )ab a b + −− e fazendo (1 )(1 ) ab ab a b α =+− − (e, portanto, (1 )(1 ) 1(1 )(1 ) ab ab a b α −− −= + −− ) obtemos (,,) (,) (1 )(1 ) c VAR a b c VAR c cc αα αα == +− − . 18 Mas (,)VAR a b α =, ou seja, (,,) (, (,))VAR a b c VAR c VAR a b=. Logo, estamos a exprimir a mensagem de “grau” 4 à custa da mensagem de “grau” 3. Generalizando para nós de grau n: Grau n: 12 1 1 2 1 (, , , ) (, (, , )) nn VAR f f f VAR f VAR f f −− =…… Quanto aos nós de paridade passa-se algo de semelhante: Grau 3: (,) (1 ) (1 )PAR a b a b b a = −+ − Grau n: 12 1 1 2 1 (,,, ) (, (,, )) nn PARx x x PARx PARx x −− =…… Vejamos como se chega a estas conclusões. Em nós de grau 3 (ver Fig. 14b) a mensagem (isto é, a função PAR(a,b)) é obtida através da Eq. (10): [] 1 (,) 1 (1 2)(1 2) 2 (1 ) (1 ) PAR a b a b a ab b ab abba = −− − =− +− = =−+− E se o nó de paridade tiver, por exemplo, grau 4 (ver Fig. 15)? A mensagem que envia é [] 1 (,,) 1(12)(12)(12) 2 PARabc abc=−− − − . ≡ PAR(a,b,c) + f j a c b + + f j PAR( β ,c) a b β c Fig. 15 A função PAR em nós de paridade de grau 4. Mas, fazendo (1 2 )(1 2 ) 1 2ab β −−=− (isto é, (,)PAR a b β =), então [] 1 (,,) 1(12)(12) (,) 2 (, (,)) PAR a b c c PAR c PAR c PAR a b ββ = −− − = = = Mais uma vez conseguimos exprimir a mensagem de um dado “grau” à custa da mensagem de um “grau” inferior. 19 3.1.3. Simplificação: o algoritmo “max-product” Regressemos ao nó de paridade de grau 3 da Fig. 14b. A mensagem transmitida resulta de um produto (cf. Eq. (10)) que, como se viu, vale 3(,) (1 ) (1 ) j rPARababba = =−+−. Uma simplificação do algoritmo substitui este cálculo pelo máximo das duas parcelas: ( ) 3max (1 ), (1 ) j rabba≈−−. Com nós de paridade de grau superior as multiplicações da Eq. (10) são simplificadas de maneira idêntica. Como? Lembrando-nos da Eq. (11) tomamos apenas o valor máximo dos diversos produtos envolvidos, ( ) max (1 )(1 ) , (1 )(1 ) , (1 )(1 ) , ji r abcbaccababc≈−−−−−−…………. (12) A este algoritmo simplificado, em que as mensagens dos nós de variáveis resultam de um produto (Eq. (9)) e as mensagens dos nós de paridade são um máximo, dá-se o nome de… algoritmo “max-product”, evidentemente. 3.1.4. Ciclos e aproximações As equações de actualização de mensagens apresentadas produzem estimativas exactas das probabilidades a posteriori ao fim da primeira (e única) iteração se o grafo de Tanner não contiver ciclos [7]. Em grafos com ciclos, uma situação muito vulgar, o procedimento de cálculo é iterativo e as estimativas das probabilidades deixam de ser exactas para passarem a ser apenas aproximações, que são tanto melhores quanto mais compridos forem os ciclos. A convergência do algoritmo deixa de estar garantida mas mesmo assim ele funciona muito bem (admiravelmente bem, até…). O código da Fig. 3 contém ciclos: por exemplo, x2 → f1 → x3 → f2 → x2 é um ciclo de comprimento 4 e x2 → f1 → x3 → f3 → x4→ f2→ x2 é um ciclo de comprimento 6. Como em grafos bipartidos os nós de uma dada classe (variáveis ou paridade) não estão ligados entre si, os ciclos, se existirem, têm sempre comprimento par (no mínimo 4). 3.2. Regras de actualização de mensagens logarítmicas Até agora considerámos que as mensagens representam estimativas de probabilidades. Porém, quando as variáveis são binárias muitas vezes é preferível fazer circular mensagens que representem quocientes de probabilidades ou o seu logaritmo (LLR). Nesse caso as equações de actualização de mensagens (Eqs. (6) e (7)) terão de ser adequadamente modificadas. Consideremos então as seguintes definições: (| 1) ln ln ( ) (| 0) 1 ii i i ii i py x p Lp py x p === =− (canais binários simétricos) (1) ( ) ln ln (0) 1 ij ij ij ij ij rr Lr rr == − (1) ( ) ln ln (0) 1 ij ij ij ij ij qq Lq qq == − Partindo da Eq. (6) facilmente obtemos a expressão das mensagens emitidas pelos nós de variáveis: 20 (1) ()ln (1 ) (0) (1) ln ln 1(0) ij i j i jj ij ij i j i jj ji i iji jj Kp r Lq Kpr r p pr ′ ′≠ ′ ′≠ ′ ′ ′≠ = = − =+ − ∏ ∏ ∑ Ou seja, ( ) ( ) ( ) ij i j i jj L qLp Lr ′ ′≠ =+ ∑. Substituímos, portanto, multiplicações por somas, o que é bastante mais simples. Quanto à mensagem dos nós de paridade não é tão fácil chegar à expressão final. Começamos com a Eq. (7) e escrevemos ( ) () 112 (1) ()ln ln (0) 112 ij ji ii ji ji ij ii q r Lr rq ′ ′≠ ′ ′≠ −− == +− ∏ ∏. Neste ponto temos de introduzir a função tangente hiperbólica tanh( ) x x x x ee xee − − − =+ (quem diria?!), a partir da qual podemos obter as seguintes igualdades: 1 tanh( 2) 1 x x e xe − = + 111 tanh ( ) ln 21 x x x − + = − Agora, sendo por definição ()ln 1 ij ij ij q Lq q = − então também é () () 1 ij ij Lq ij Lq e qe =+, donde se tira que () () () () 12 12 1 () 1tanh 2 1 ij ij ij ij Lq ij Lq Lq ij Lq e qe Lq e e −=− = + ⎛⎞ − ==− ⎜⎟ +⎝⎠ Como a tangente hiperbólica é uma função ímpar então também podemos escrever () () 12 tanh 2 () ij ij ij Lq q Lq ⎛⎞ − =− = ⎜⎟ ⎝⎠ =Φ onde definimos a função auxiliar ( ) () tanh 2 x xΦ= − . Estamos prontos para retomar a expressão da LLR L(rji) e obter finalmente 21 ( ) () ( ) () () 1 112 1tanh()2 ( ) ln ln 112 1tanh()2 2tanh tanh ( ) 2 ij ij ii ii ji ij ij ii ii ij ii qLq Lr qLq Lq ′′ ′′ ≠≠ ′′ ′′ ≠≠ −′ ′≠ −− − − == = +− + − ⎛⎞ =−− ⎜⎟ ⎜⎟ ⎝⎠ ∏ ∏ ∏∏ ∏ e também a expressão equivalente () 1 () ( ) ji i j ii Lr Lq −′ ′≠ ⎛⎞ =Φ Φ ⎜⎟ ⎜⎟ ⎝⎠ ∏. Em resumo: Mensagens logarítmicas • Do nó de variável xi para o nó de paridade fj: () () () ij i j i jj L qLp Lr ′ ′≠ =+ ∑ (13) • Do nó de paridade fj para o nó de variável xi: () () 1 1 ()2tanh tanh ( )2 () ji i j ii ij ii Lr Lq Lq −′ ′≠ −′ ′≠ ⎡ ⎤ =−− = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎡⎤ =Φ Φ ⎢⎥ ⎢⎥ ⎣⎦ ∏ ∏ (14) Nota 1: A Eq. (14) pode escrever-se de uma maneira mais elegante e até mais memorizável: ( ) ( ) () ( ) j iij ii Lr Lq ′ ′≠ Φ=Φ ∏ Nota 2: Se tivéssemos definido 1 () ln x Lx x − = em vez de () ln 1 x Lx x = − a Eq. (14) escrever-se-ia com mais simplicidade: () 1 ()2tanh tanh( )2 ji i j ii Lr Lq −′ ′≠ ⎡⎤ =⎢⎥ ⎢⎥ ⎣⎦ ∏ ou ( )() tanh ( ) 2 tanh ( ) 2 ji i j ii Lr Lq′ ′≠ =∏. No fim de todas as iterações calcula-se a LLR final somando todas as LLR que confluem na variável: ()() () () ii iji j Lx Lq Lp Lr == =+ ∑ y A expressão anterior mostra que a LLR a posteriori é igual à soma de uma componente fixa intrínseca à variável, L(pi), com uma componente que lhe é extrínseca e resultou da transferência de mensagens, ( ) ji j Lr ∑. 22 3.2.1. Canais com ruído AWGN As expressões anteriores são válidas para outros canais além daquele que temos considerado até aqui (o canal binário simétrico): há só que usar o valor adequado da LLR a priori (| 1) ln (| 0) ii ii py x py x = = ou (| 1) ln (| 1) ii ii py x py x = + = −. Assim, se se enviar uma sequência binária xi = ±1 através de um canal AWGN com ruído de média nula e variância σ2 e se se receber a sequência de valores reais yi, a LLR a priori , isto é, aquilo de que necessitamos para iniciar os cálculos, vale () () () () 2 22 2 22 2 (| 1) ()ln(| 1) 12 exp 1 2 ln 12 exp 1 2 2 ii iii i i i py x Lp py x y y y πσ σ πσ σ σ = + == =− ⎡ ⎤ −− ⎢ ⎥ ⎣ ⎦ == ⎡ ⎤ −+ ⎢ ⎥ ⎣ ⎦ = O ruído à saída de um filtro adaptado no receptor tem variância 20 2c N E σ =, em que N0/2 é a densidade espectral de potência do ruído e Ec = RcEb é a energia de cada bit codificado (sendo Eb a energia de cada bit antes da codificação e Rc = k/n a taxa do código). Portanto, 00 ()4 4 ccb ii i ERE Lp y y NN == . Agora é só usar este valor nas equações de actualização. 3.2.2. Simplificações: o algoritmo “min-sum” As razões LLR são usadas para simplificar cálculos, nomeadamente para substituir multiplicações por somas. Ora, se bem que tenhamos substituído multiplicações por adições no cálculo das mensagens de variáveis, as multiplicações subsistem no cálculo das mensagens dos nós de paridade. Porém, não por muito tempo! Assim, definindo uma nova função auxiliar, ( ) () lntanh 2xxΨ=− ⎡ ⎤ ⎣ ⎦, x > 0 (ver Fig. 16), e sabendo que qualquer número real y é igual ao produto do seu módulo pelo seu sinal, sgn( )yyy=, a Eq. (14) pode escrever-se () ()(1) sgn() () j d ji ij ij ii ii Lr Lq Lq ′′ ′ ′≠ ≠ ⎛⎞ ⎛⎞ ⎡⎤ =− Ψ Ψ ⎜⎟ ⎜⎟ ⎣⎦ ⎜⎟ ⎜⎟ ⎝⎠ ⎝⎠ ∑ ∏ (15) em que dj é o grau do nó. Acontece que, como se vê na Fig. 16, Ψ é uma função positiva fortemente decrescente pelo que o somatório das funções Ψ é aproximadamente igual ao termo dominante, correspondente ao menor dos |L(qji)| envolvidos. Além disso, a 23 função Ψ é igual à sua inversa, Ψ-1(x) = Ψ(x), isto é, Ψ(Ψ(x)) = x. Logo, a expressão acima simplifica-se em () () () ()(1) sgn ( ) max ( ) (1) sgn ( ) min ( ) j j d ji i j i j ii ii dij ij ii ii Lr Lq Lq Lq Lq ′′ ′≠ ′≠ ′′ ′≠ ′≠ ⎛⎞ ⎛⎞ ⎡⎤ ≈− Ψ Ψ = ⎜⎟ ⎜⎟ ⎣⎦ ⎜⎟ ⎝⎠ ⎝⎠ ⎛⎞ ⎡⎤ =− ⎜⎟ ⎣⎦ ⎜⎟ ⎝⎠ ∏ ∏ 01234 0 1 2 3 x Ψ(x) Ψ (x) = -ln(tanh(x/2)) Fig. 16 A função auxiliar ( ) () lntanh 2xxΨ=− ⎡ ⎤ ⎣ ⎦. A esta forma aproximada (mas bastante mais simples) de cálculo dá-se o nome de… “min-sum algorithm”: Algoritmo “min-sum” • Do nó de variável xi para o nó de paridade fj: () () () ij i j i jj Lq Lp Lr ′ ′≠ =+ ∑ (16) • Do nó de paridade fj para o nó de variável xi: () ()(1) sgn ( ) min ( ) j d j iijij ii ii Lr Lq Lq ′′ ′≠ ′≠ ⎛⎞ ⎡⎤ =− ⎜⎟ ⎣⎦ ⎜⎟ ⎝⎠ ∏ (17) Quer este algoritmo quer o algoritmo “max-product” só diferem do algoritmo SP “normal” no modo de cálculo, aproximado, das mensagens dos nós de paridade. As mensagens dos nós de variáveis, essas, são calculadas da maneira “normal”. Exemplo 5 A figura seguinte apresenta as expressões de actualização de nós com os algoritmos simplificados “max-product” (com probabilidades) e “min-sum” (com LLRs) no caso de nós de grau 3. 24 q c r a r b (1 )(1 ) ab cab a b rr qrr r r =+− − () () () cab Lq Lr Lr = + ( ) max (1 ), (1 ) cabba rqqqq=−− ( ) ( ) ( ) () sgn ( )sgn ( )min ( ),( ) cabab Lr Lq Lq Lq Lq=− r c q a q b “max-product” “min-sum” 4. Exemplo numérico de aplicação Vamos então a um exemplo numérico considerando um canal binário simétrico (BSC) e o codificador11 (7,4) da Fig. 3. A compreensão do exemplo tornará fácil a aplicação do algoritmo da soma-e-produto a outros tipos de canal, como o canal de ruído AWGN. Suponhamos que a palavra de código x = 1 1 0 0 0 1 0 foi transmitida através de um canal BSC com p = 0,1, que a transformou na sequência y = 1 1 0 1 0 1 0. Ou seja, o quarto bit está errado (mas o descodificador ainda não sabe!…). Como é que poderemos corrigir o bit errado usando transferência de mensagens ao longo das linhas do grafo de Tanner do codificador? Como se mostra na Fig. 17, cada nó-folha pi envia do canal para o seu argumento xi uma mensagem fixa igual ao valor da respectiva probabilidade a priori pi: (| 1) ii i p yx p = =. Por exemplo, x1 recebe a informação a priori 11 (1|1)0,9py x = == e x3 recebe 33 (0|1)0,1py x=== . Por sua vez cada variável xi difunde a mensagem que recebeu do canal pelos nós de paridade aos quais está ligada. Assim, por exemplo, 21 22 20,9 qq p == == 51 53 50,1 qq p = = == A Fig. 17 mostra os valores das primeiras mensagens recebidas pelos nós de paridade. Que mensagens vão eles agora enviar aos nós de variáveis? Consideremos f1, por exemplo. Este nó recebeu estimativas de x1, x2, x3 e x 5. Então para x1 enviará uma estimativa baseada nas estimativas que recebeu das outras variáveis (x2, x3 e x5), para x2 enviará uma estimativa que se baseia nas que recebeu de x1, x3 e x5, e para x3 e x5 fará de modo idêntico. Em particular, a mensagem que x1 recebe de f1 é dada, de acordo com a Eq. (10), por 11 Este código não é, de facto, um código LDPC mas para o caso é irrelevante. 25 {} [] 11 1 2,3,5 21 31 51 11(12) 2 11 (1 2 )(1 2 )(1 2 ) 2 0,756 i i rq qqq ∈ ⎡⎤ ⎢⎥ =− − = ⎢⎥ ⎣⎦ =−− − − = = ∏ + f 1 + f 2 +f 3 x 3 p 3 0,1 x 1 p 1 0,9 x 5 p 5 0,1 x 7 p 7 0,1 x 2 p 2 0,9 x 4 p 4 0,9 x 6 p 6 0,9 0,9 0,9 0,9 0,1 0,1 0,9 0,9 0,1 0,1 0,9 0,1 Fig. 17 Mensagens iniciais enviadas pelas variáveis aos nós de paridade fj. Identicamente obteríamos as mensagens de f1 para as suas restantes variáveis, 12 0,756r= 13 0,244r = 15 0,244r = , e as mensagens de f2 e f3 também, 22 0,244r= 23 0,756r = 24 0,244r = 26 0,244r = 33 0,756r= 34 0,244r = 35 0,756r = 37 0,756r = , como a Fig. 18 mostra. Em seguida cada variável envia aos nós de paridade o produto normalizado das mensagens que recebeu, como se ilustra na Fig. 19 para a variável x2: + f 1 + f 2 +f 3 x 3 p 3 0,1 x 1 p 1 0,9 x 5 p 5 0,1 x 7 p 7 0,1 x 2 p 2 0,9 x 4 p 4 0,9 x 6 p 6 0,9 0,756 0,756 0,244 0,244 0,756 0,244 0,244 0,756 0,244 0,244 0,756 0,756 Fig. 18 Primeiras mensagens enviadas pelos nós de paridade aos nós de variáveis. 32 22 2 0,756 () 0,244 rx ⎡⎤ =⎢⎥ ⎣⎦ 23 3 0,244 () 0,756 rx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 24 4 0,756 () 0,244 rx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 26 6 0,756 () 0,244 rx ⎡⎤ =⎢⎥ ⎣⎦ 33 3 0,244 () 0,756 rx ⎡⎤ =⎢⎥ ⎣⎦ 34 4 0,756 () 0,244 rx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 35 5 0,244 () 0,756 rx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 37 7 0,244 () 0,756 rx ⎡⎤ =⎢⎥ ⎣⎦ + x1 x2 x3 x5 f1 0,244 0,756 ⎡⎤ ⎢⎥ ⎣⎦ 0,756 0,244 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 0,756 0,244 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 0,244 0,756 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ Fig. 25 Primeiras mensagens enviadas pelo nó de paridade f1 aos nós de variáveis a que está ligado. Uma pausa Antes de prosseguir vamos parar um pouco para constatar que a Eq. (18) conduz ao mesmo resultado que obteríamos se usássemos a notação alternativa simplificada rij e qij. Se com essa equação quisermos determinar 11 11 1 (1)rrx = = deveremos considerar apenas a soma que multiplica δ(x1 + 1) (porquê? Porque com x1 = 1 é δ(x1 + 1) = δ(0) = 1 e δ(x1) = δ(1) = 0). Ora como (0) 1 ij ij qq = − e (1) ij ij qq = a Eq. (18) conduz-nos a 11 21 31 51 21 31 51 21 31 51 21 31 51 (1)(1)(1)(1)(1)(1)rqqqqqqqqqqqq=− − +− − + − − + Ora compare esta expressão com a Eq. (11). Não nota semelhanças? Voltemos às iterações… Tínhamos terminado a primeira e vamos agora iniciar a segunda. Nesta, cada variável xi envia a cada nó de paridade uma nova mensagem calculada com base na estimativa inicial fixa p(yi|xi) e nas diferentes mensagens que recebeu dos outros nós de paridade. Por exemplo, de x2 para f1 e f2 vamos ter, respectivamente, 21 2 21 2 2 22 2 21 21 0,1 0,756 0,076 () ( |) () 0,9 0,244 0,220 qx Kpyx rx K K ⎡ ⎤⎡ ⎤ ⎡ ⎤ =•=•= ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣ ⎦⎣ ⎦ ⎣ ⎦ produto elemento-a-elemento 22 2 22 2 2 12 2 22 22 0,1 0,244 0,024 () ( | ) () 0,9 0,756 0,680 qx Kpyx rx K K ⎡ ⎤⎡ ⎤ ⎡ ⎤ =•=•= ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣ ⎦⎣ ⎦ ⎣ ⎦ 33 o que dá, depois de normalizar dividindo cada elemento pela soma dos dois, 21 2 0,256 () 0,744 qx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 22 2 0,035 () 0,965 qx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ como se mostra na Fig. 26. E o algoritmo prosseguiria, iteração após iteração… Mensagens que f 1 e f2 enviam a x2 Mensagem enviada por x2 a f1 Mensagem enviada por x2 a f2 1 x2 f1 + + f2 0,244 0,756 ⎡⎤ ⎢⎥ ⎣⎦ 0,756 0,244 ⎡⎤ ⎢⎥ ⎣⎦ 0,1 0,9 ⎡⎤ ⎢⎥ ⎣⎦ 2 x2 f1 ++ f2 0,256 0,744 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 0,756 0,244 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 0,1 0,9 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 3 x2 f1 f2 0,244 0,756 ⎡ ⎤ ⎢ ⎥ ⎣ ⎦ 0,035 0,965 ⎡⎤ ⎢⎥ ⎣⎦ 0,1 0,9 ⎡⎤ ⎢⎥ ⎣⎦ ++ Fig. 26 Novas mensagens enviadas por x2 aos nós de paridade f1 e f2. No exemplo em que usámos mensagens escalares foi apresentada a Tabela 1 com os valores de LLR a posteriori obtidos durante cinco iterações. É claro que com as mensagens vectoriais de agora devemos obter exactamente os mesmos resultados. Vamos confirmá-lo. Por exemplo, vimos que ao fim da primeira iteração as mensagens 22 22 (| 0) 0,1 (| 1) 0,9 py x py x = ⎡⎤ ⎡⎤ = ⎢⎥ ⎢⎥ =⎣⎦ ⎣⎦ 12 2 0,244 () 0,756 rx ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ 22 2 0,756 () 0,244 rx ⎡⎤ =⎢⎥ ⎣⎦ chegaram a x2; então, para calcular a LLR a posteriori temos de primeiro calcular as probabilidades a posteriori  multiplicando as três mensagens elemento-a-elemento, 0,1 0,244 0,756 0,018 0,9 0,756 0,244 0,166 ×× ⎡⎤⎡⎤ = ⎢⎥⎢⎥ ×× ⎣⎦⎣⎦ ,  normalizando, 2 2 (0|)0,018 0,184 0,10 (1|)0,166 0,184 0,90 px px = ⎡⎤ ⎡ ⎤⎡ ⎤ == ⎢⎥ ⎢ ⎥⎢ ⎥ = ⎣ ⎦⎣ ⎦ ⎣⎦ y y e depois achar o logaritmo natural do quociente adequado, 2 22 (1|) 0,90 (|) ln ln 2,20 (0|)0,10 px Lx px = === = y yy. 34 Não é este o valor que consta da Tabela 1? 5. Referências [1] R. G. Gallager, “Low-density parity-check codes”, IRE Transactions on Information Theory, vol. IT-8, pp. 21-28, Janeiro de 1962. [2] R. G. Gallager, Low-density parity-check codes, Monograph, M.I.T. Press, 1963. (Tese de Doutoramento) [3] C. Berrou, A. Glavieux e P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding”, Proceedings of the IEEE International Conference on Communications (ICC '93), Maio de 1993, pp. 1064-1070. [4] R. M. Tanner, “A recursive approach to low complexity codes", IEEE Transactions on Information Theory, Vol. IT-27, nº 5, pp. 533-547, Setembro de 1981. [5] N. Wiberg, H.-A. Loeliger e R. Kötter, “Codes and iterative decoding on general graphs”, European Transactions on Telecommunications, vol. 6, pp. 513-525, Setembro/Outubro de 1995. [6] N. Wiberg, “Codes and decoding on general graphs”, Dissertação de Doutoramento, Linköping Univ., Linköping, Suécia, 1996. [7] F. R. Kschischang, B. J. Frey e H.-A. Loeliger, “Factor graphs and the sum-product algorithm”, IEEE Transactions on Information Theory, Vol. 47, nº 2, pp. 498-519, Fevereiro de 2001. [8] F. R. Kschischang, “Codes defined on graphs”, IEEE Communications Magazine, pp. 118-125, Agosto de 2003. [9] H.-A. Loeliger, “An introduction to factor graphs”, IEEE Signal Processing Magazine, pp. 28-41, Janeiro de 2004. [10] L. R. Bahl, J. Cocke, F. Jelinek e J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. on Information Theory, pp. 284-287, Março de 1974. [11] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers, Inc., 1988. [12] R. J. McEliece, D. J. C. MacKay e J.-F. Cheng, “Turbo Decoding as an Instance of Pearl’s “Belief Propagation” Algorithm”, IEEE Journal on Selected Areas In Communications, Vol. 16, nº 2, pp.140-152, Fevereiro de 1998. [13] J. Fan, “Lecture 2 on LDPC codes”, Universidade de Stanford, EUA. Disponível online em http://www.stanford.edu/class/ee379b/class_reader/lecture2_4print.pdf. Acedido em 25-6-05.