Introdução aos códigos LDPC e seu desempenho

Os códigos de verificação de paridade de baixa densidade (LDPC), descobertos pela primeira vez por Robert Gallager em sua tese de doutorado de 1960 e redescobertos posteriormente na década de 1990, tornaram-se uma pedra angular das comunicações digitais modernas. Eles são empregados em padrões como DVB-S2, Wi-Fi (IEEE 802.11n/ac/ax), 5G NR e comunicações por satélite. Os códigos LDPC são definidos por uma matriz de verificação de paridade esparsa que corresponde a um gráfico de Tanner bipartido com nós variáveis (representando bits de código) e nós de verificação (representando equações de paridade). O algoritmo de de decodificação iterativa, tipicamente propagação de crença (BP) ou uma variante de soma mínima, passa mensagens ao longo das bordas deste gráfico.

O desempenho de um código LDPC é caracterizado frequentemente por seu threshold—o nível máximo de ruído do canal (ou mínimo SNR) no qual a probabilidade de erro de decodificação pode ser impulsionado arbitrariamente perto de zero, uma vez que o comprimento do código tende a infinito. Aproximar-se do limite de Shannon requer um design cuidadoso da estrutura do código. Entre os parâmetros de projeto mais influentes estão as distribuições de graus [] de nós variáveis e de verificação, que descrevem quantas bordas cada tipo de nó possui. Otimizar essas distribuições pode empurrar o limiar mais próximo da capacidade do canal para um determinado modelo de canal.

Este artigo fornece uma exploração aprofundada da otimização da distribuição de graus para códigos LDPC. Primeiro revisamos os fundamentos da decodificação e limiares LDPC. Depois dissecamos o papel das distribuições de graus e examinamos técnicas de otimização clássicas, como a evolução da densidade e gráficos EXIT. Posteriormente, adaptamos a discussão a modelos de canais específicos – canal simétrico binário (BSC), canal gaussiano branco aditivo (AWGN), canal de apagamento binário (BEC) e canais de de desvanecimento Rayleigh – mostrando como as distribuições devem ser adaptadas. Finalmente, tocamos em considerações de comprimento finito e desenho de código prático, apoiados por referências externas para leitura posterior.

Entender os códigos e limiares LDPC

Um código LDPC de comprimento ]n e dimensão kH[m × n] matriz de verificação de paridade H[m[]m[]nn] − ]k[ (assumindo o nível completo).A matriz é esparsa: o número de 1's é linear em n[FLT[FLT[[FLT][FLT][FL] [N] [FLT] [FLT] [FL] [F:221).

O algoritmo de decodificação opera iterativamente trocando mensagens ao longo destas bordas. Para o BEC, as mensagens são apagações, bits ou símbolos desconhecidos. Para canais simétricos como BSC e AWGN, as mensagens são razões de tipo de log (LLRs). O algoritmo converge quando todas as verificações de paridade são satisfeitas ou após um número máximo de iterações. O threshold[] é definido através da evolução da densidade: para um determinado conjunto de código (definido por distribuições de graus), pode- se calcular o parâmetro máximo do canal (por exemplo, probabilidade cruzada p] para BSC, variância de ruído σ2 para AWGN, probabilidade de eliminação ε para BEC), de modo que a probabilidade de erro de decodificação tende a zero como n → Ñ. Thresholdsholds são uma medida fundamental do desempenho asympt como um conjunto prático e um guia para um conjunto de um conjunto.

Papel das distribuições de graus

As distribuições de graus são tipicamente representadas por polinômios. Para nós variáveis, deixe λ(x]] = i]] λ:]]]i] ] [FT3][F:3T3][F:T3T[F:T3T] [F:T3T3T[F:T[F:T:T:T:T

A escolha das distribuições afeta criticamente o fluxo de informação extrínseca durante a decodificação. Um nó variável de grau d[v[ coleta informações de d[[v[[]incidente check nodos e a observação do canal; então envia mensagens atualizadas de volta. Nós variáveis de alto grau recebem mensagens de verificação mais diversas, que podem acelerar a convergência, mas também propagam mais erros se as mensagens de verificação não forem confiáveis. Nós de baixo grau são mais robustos ao ruído, mas convergem lentamente. Da mesma forma, verifique nós de grau dc]c[]] realizar uma operação de paridade; nós de verificação de grau superior podem lidar mais longos, mas também criam ciclos no gráfico, desempenho potencialmente degradativo sob decodificação iterativa.

Distribuição de Grau de Nó Variável

A distribuição de graus de nó variável tem uma forte influência sobre o limiar de decodificação ] do código. No trabalho seminal de Luby, Mitzenmacher, Shokrolahi e Spielman (1998) sobre códigos irregulares de LDPC, foi mostrado que nós variáveis com uma mistura de graus – alguns altos, alguns baixos – podem atingir limiares extremamente próximos do limite de Shannon para o BEC. A intuição é que os nós de alto grau, que recebem muitas mensagens, rapidamente aprendem o seu valor correto e ajudam os nós de baixo grau através de nós de verificação. Para o canal AWGN, distribuições irregulares com otimização cuidadosa alcançaram limiares dentro de 0,0045 dB de capacidade. Os padrões comuns incluem alguns nós variáveis de alto grau (por exemplo, grau 20, 30) e muitos nós de baixo grau (por exemplo, grau 2, 3). No entanto, a presença de nós de grau 2 pode criar um piso de erro devido a pequenos ciclos; muitas vezes, os nós de grau-2 são evitados ou limitados.

Verificar a Distribuição de Graus

Os graus de nó de verificação também importam, embora o seu impacto seja geralmente secundário em comparação com nós variáveis. Para o BEC, a distribuição ideal do nó de verificação é concentrada em torno de um único grau (frequentemente 4–10) para maximizar o limiar, como mostrado por Shokrollahi (2002). Para os canais AWGN, os graus de verificação normalmente variam de 3 a 10; os graus mais altos aumentam a complexidade do nó de verificação, mas podem melhorar o limiar. Uma escolha comum é uma distribuição de grau concentrada, por exemplo, ρ](x4 ]p3 x[pp[F1]pp[F]p]p [F1]p [Fltp]p]p [Flt[F.

Métodos de otimização para distribuições de graus

Encontrar distribuições de graus ideais é um problema de otimização não-convexa que foi abordado usando várias técnicas analíticas e numéricas. Os três métodos mais comuns são a evolução da densidade (DE), gráficos extrínsecos de transferência de informação (EXIT) e aproximações de programação linear (LP).

Evolução da densidade

A evolução da densidade, introduzida por Richardson e Urbanke (2001), rastreia a função de densidade de probabilidade (pdf) das mensagens trocadas durante a decodificação iterativa, assumindo um gráfico livre de ciclo (árvores). Para o BEC, as mensagens são binárias (erasura ou conhecidas), por isso DE reduz para o rastreamento da probabilidade de eliminação através do gráfico. Para os canais AWGN, DE rastreia o pdf dos LLRs, que sob a aproximação gaussiana simétrica reduz para o rastreamento da média mx]) e ρ(([[FLT: 8]x[FLT: 3]xxx[Flitação]x[FLT: 5]x[Flitação]x[Constrição]]] esta pode ser usada para a taxa linear.

Gráficos de EXIT

Os gráficos EXIT, desenvolvidos por dez Brink (2001), fornecem uma ferramenta gráfica para analisar o comportamento de convergência dos decodificadores iterativos. Eles plotam as informações mútuas (MI) transferidas de nós variáveis para verificar nós versus MI transferidos de nós de verificação para nós variáveis. As curvas resultantes, chamadas curvas características, não devem se cruzar para a decodificação ter sucesso. A otimização das distribuições de graus usando gráficos EXIT envolve a correspondência da área sob a curva de nó variável para a área sob a curva de nó de verificação, com a diferença de área relacionada com o gap para a capacidade. Os gráficos EXIT são especialmente populares para os canais AWGN, porque são computacionalmente mais simples do que o DE completo e dão insight intuitivo. No entanto, eles dependem da aproximação gaussssiana das distribuições LLR, que se torna menos precisa para ruído severo ou distribuições irregulares.

Programação Linear e Outras Abordagens

Para o BEC, o problema de otimização pode ser lançado como um programa linear porque a condição DE reduz a uma desigualdade linear sobre os coeficientes de λ[ e ρ. A programação linear produz distribuições globalmente ótimas (sobre um determinado conjunto de graus) de forma eficiente. Para canais gerais, as restrições são não lineares, por isso são utilizadas heurísticas, tais como recozimento simulado, algoritmos genéticos ou métodos baseados em gradientes. Avanços recentes usam aprendizado de máquina (por exemplo, aprendizagem de reforço) para pesquisar o espaço de distribuições de graus. Outra abordagem é usar transferência extrínseca de informações (EXIT) com uma função de custo baseada na propriedade da área. Independentemente do método, o resultado é um conjunto de pares de graus (d]v, dc[[) e frações que maximizam um limite para um canal específico.

Otimização para diferentes modelos de canais

Diferentes canais têm propriedades estatísticas diferentes, que afetam a natureza das mensagens trocadas e, portanto, as distribuições de graus ideais. Abaixo discutimos quatro modelos de canais principais: BEC, BSC, AWGN e Rayleigh desvanecendo.

Canal de Borracha Binário (BEC)

O BEC é o canal não trivial mais simples: com probabilidade ε um pouco é apagado (desconhecido), e de outra forma recebido corretamente. O limite é o máximo ε tal que a decodificação tenha sucesso. Para o BEC, as distribuições de graus ideais são conhecidas analiticamente através da programação linear. Em 2001, Luby et al. mostraram que os códigos LDPC irregulares podem atingir a capacidade (ε = 1 - ]R[[]) assintoticamente. A distribuição de nó variável ótima inclui nós de alto grau (por exemplo, grau até 50 ou 100) e uma grande fração de nós de grau-2. No entanto, os nós de grau-2 criam uma vulnerabilidade "paragem" em comprimentos finitos, levando a um piso de erro. Os desenhos práticos para o BEC (por exemplo, códigos de raptor) usam distribuições de grau com apenas alguns nós de grau-2 e uma cauda pesada. A distribuição de nó de grau 5 é tipicamente concentrada em um único grau, muitas vezes d[FT] o conjunto [dital] [dilo de 1/2T

Canal simétrico binário (BSC)

As distribuições de graus ideais para BSC são mais complexas porque as mensagens são binárias (decisões difíceis) num decodificador de decisão dura (por exemplo, o algoritmo de Gallager A/B) ou valores suaves se usar BP com LLRs. Para a decodificação de decisões difíceis, as distribuições de graus são normalmente regulares (todos os nós variáveis do mesmo grau, todos os nós de verificação do mesmo grau) porque a irregularidade fornece pouco ganho. O código LDPC regular ideal para BSC sob o algoritmo de Gallager tem grau variável 3 e verifica o grau 6 para a taxa 1/2, atingindo um limiar próximo de p 7,6%. Para o BP de decisão suave em BSC (usando LLLRs convertidos de bits rígidos), distribuições irregulares podem melhorar o limiar, mas o ganho é modesto em comparação com AWGN. Research by Chung, Forney, et al. (2001) dá frequentemente distribuições otimizadas para BSCs de bits rígidos, distribuições irregulares podem melhorar o limite [0,1 para o uso da AFLT].

Canal de ruído gaussiano branco aditivo (AWGN)

O canal AWGN é o modelo mais estudado. O objetivo é maximizar o limiar SNR (muitas vezes expresso em ]Eb/N0[][[]][[[/N[[[[[[[[[]][[[[T:5]]]]]]][[[[[[[[[[[FLT:FT]]]][[[[[[[[[][[[[][[[[]]]]]]][[[[[[[[[[[[[[[[FLT

Canal de desvanecimento de Rayleigh (com ou sem CSI)

Num canal de desvanecimento do Rayleigh, a amplitude do sinal recebido varia devido ao desvanecimento. Com a informação perfeita do estado do canal (CSI) no receptor, o canal eficaz é um conjunto de subcanais gaussianos com diferentes ganhos. A distribuição de graus deve adaptar- se às estatísticas de desvanecimento. Como mostrado por Hou, Siegel e Milstein (2003), os códigos LDPC irregulares com distribuições de graus otimizadas podem atingir limiares que se aproximam da informação mútua média do canal desvanecimento. A visão chave é que os nós variáveis que experimentam desvanecimentos profundos necessitam de mais proteção dos nós de verificação conectados, implicando uma necessidade de nós variáveis de alto grau para a informação de agrupamento. A distribuição ideal é mais pesada do que para AWGN; os nós de alto grau (por exemplo, 20–30) aparecem com maior frequência. Os graus de verificação são tipicamente concentrados em torno de 4–8. Para sistemas sem CSI (desvanecimento não coerente), o problema é mais desafiador e as distribuições de graus são muitas otimizadas para os gráficos específicos do Doppler usando gráficos EXIT. Investigação por A. Grant e outros demonstraram que os

Tópicos Avançados em Otimização de Distribuição de Graus

Efeitos de Comprimento Finito e Piso de Erro

O desenho de guias de limiares assintóticos, mas os códigos práticos têm comprimento finito n (por exemplo, 648 a 1944 bits em 5G). No comprimento finito, o piso de erro - uma região de probabilidade de erro muito baixa que não diminui rapidamente com o SNR - torna- se crítico. O piso de erro dos códigos LDPC é causado principalmente por pequenos conjuntos de parada (para o BEC) ou conjuntos de armadilhagem (para o AWGN). As distribuições de graus com muitos nós variáveis de baixo grau (especialmente grau 2) são propensas a tais estruturas. Para atenuar o piso de erro, a otimização deve incluir restrições na circunferência do gráfico (comprimento mínimo do ciclo) e as propriedades espectrais do código. Algumas abordagens adotam uma otimização multi- objectiva: maximizando o limiar enquanto minimizam o número de pequenos conjuntos de armadilhagem. Isto geralmente leva a distribuições com menos nós de grau-2 e um grau mais concentrado de nó variável. Os códigos baseados em protógrafo LDPC, que definem o código por uma pequena base de controle, permitem a obtenção de graus de graus de distribuição de distribuição de

Considerações sobre a implementação

Enquanto nós de alto grau melhoram os limiares, eles aumentam a complexidade de decodificação. Para cada iteração, o número de operações por borda é proporcional ao grau. Um nó variável de grau 30 requer 30 adições (para atualizações LLR) por iteração, em comparação com 3 para um nó grau-3. Em hardware, as restrições de memória e largura de banda muitas vezes limitam o grau máximo em torno de 10-20. Da mesma forma, os graus de alto nível aumentam o número de operações de mín- soma ou de produto. Muitos codificadores práticos (por exemplo, para Wi-Fi) usam um conjunto restrito de graus: graus variáveis apenas 2, 3, 4, 6 e 10; graus de verificação apenas 4-8. A otimização sob tais restrições é uma área ativa. Outra questão é a perda de taxa de código devido à necessidade de bits de paridade: a taxa de projeto da fórmula de grau pode diferir ligeiramente da taxa real de construção de gráficos. O cuidado deve ser tomado para garantir que as equações de distribuição sejam consistentes.

Exemplos de Desenho de Código

Para ilustrar, considere um código de taxa- 1/2 LDPC para o canal AWGN. Usando programação linear com evolução de densidade, a seguinte distribuição (de Richardson & amp; Urbanke, 2001) é frequentemente citada:

Variable degreeFraction of edges
20.289
30.171
60.486
100.055

E verificar a distribuição do nó: [[FLT: 0]] p( x) = 0,497 x3 + 0,503 x4 (ou seja, frações de bordas incidentes ao grau 4 e 5 nós de verificação). Este conjunto tem um limite de [[FLT: 2]] E[[FLT: 3]] b[[[FLT: 4]/ N[[ 0[[[FLT: 6][[[FLT: 7] = 0, 19 dB. Em contraste, um código regular (3, 6) tem um limite em torno de 0,7 dB. O desenho irregular ganha cerca de 0,5 dB. Para o BEC, uma distribuição de taxa- 1/2 ideal (Shokrollahi, 2002) é:

Variable degreeFraction of edges
20.420
30.020
100.010
1000.550

A distribuição do nó de verificação está concentrada no grau 4 (100%). O limiar é ε = 0,499, muito próximo da capacidade de 0,5. No entanto, o nó de alto grau-100 torna o código impraticável para decodificadores de baixa complexidade.

Conclusão

A opção de perfis de graus variáveis e de verificação determina o fluxo de informação durante a decodificação iterativa e deve ser adaptada às características de ruído do canal. Para os canais de eliminação, a programação linear produz distribuições quase optimizadas com graus variáveis de cauda pesada. Para os canais de desvanecimento e desvanecimento, a evolução da densidade e os gráficos EXIT orientam o desenho, resultando frequentemente em perfis irregulares com alguns nós de alto grau. As restrições práticas, tais como o comprimento finito, o piso de erro e a complexidade da descodificação, impõem limites aos quais distribuições são viáveis, tornando a otimização um descompasso entre desempenho assintótico e implementabilidade.

Como os padrões de comunicação evoluem para um maior rendimento e menor latência, a demanda por códigos LDPC otimizados continua. Pesquisas recentes exploram a otimização baseada em aprendizado de máquina, modificações de protógrafo e otimização combinada de graus e giros. Compreendendo os fundamentos da otimização de distribuição de graus equipa os engenheiros a projetar melhores códigos para sistemas de armazenamento, satélite e sem fio de próxima geração. Para leitura posterior, veja o livro clássico "Modern Coding Theory" de Richardson e Urbanke, o papel seminal "Desenvolvimento de Códigos de Capacidade-Aproximação Irregular de Baixa Densidade" de Johnson e Weller].Para detalhes práticos de implementação, as especificações padrão 5G estão disponíveis a partir de 3GPP[T.2].