Introdução aos códigos de verificação de paridade de baixa densidade

Os códigos de baixa densidade (LDPC) estão entre os códigos de correção de erros mais poderosos nas comunicações digitais modernas. Primeiro introduzido por Robert Gallager em sua tese de doutorado de 1960, esses códigos foram amplamente esquecidos por décadas antes de serem redescobertos em meados da década de 1990. Sua capacidade de aproximar o limite de Shannon com complexidade prática de decodificação tornou-os a pedra angular de inúmeros sistemas, desde transmissões de televisão via satélite até armazenamento de flash 5G New Radio e NAND. A chave para seu desempenho está em uma matriz de verificação de paridade muito esparsa: a maioria das entradas são zero, o que simplifica os algoritmos de decodificação baseados em gráficos que podem ser implementados em hardware.

Em ambientes de alto rendimento, a decodificação baseada em software simplesmente não consegue manter o ritmo. À medida que as taxas de dados sobem para 100 Gbps e para além em redes de transporte óptico, as demandas dos decodificadores LDPC se tornam extremas. Isso tem levado a indústria a aceleradores de hardware dedicados que exploram o paralelismo em todos os níveis. Os avanços descritos neste artigo representam o estado da arte em arquiteturas paralelas de decodificação, oferecendo velocidade e eficiência para aplicações do mundo real.

Tecnologia relacionada: Para uma visão geral dos fundamentos do código LDPC, ver o artigo Wikipedia sobre códigos LDPC.

Fundo Teórico: Algoritmos de decodificação

Antes de examinar arquiteturas de hardware, é essencial entender os algoritmos que sustentam a decodificação LDPC. O algoritmo mais utilizado é o decodificador de propagação de crenças (BP), também conhecido como algoritmo de produto somatório. Ele opera em um grafo bipartido - o grafo Tanner - composto por nós variáveis (representando bits de palavra de código) e nós de verificação (representando restrições de paridade). Mensagens são passadas iterativamente entre nós, atualizando probabilidades até que as equações de paridade sejam satisfeitas ou uma contagem máxima de iteração seja alcançada.

O custo computacional da BP é substancial devido às funções tangentes hiperbólicas necessárias para cálculos de probabilidade. Uma aproximação prática é o algoritmo min-sum, que substitui a função complexa por operações de sinais e minutos. Embora isso incorre em uma pequena perda de desempenho, a simplificação é fundamental para a implementação de hardware de alta velocidade. Pesquisadores desenvolveram muitas variantes – offset min-sum, normalizado min-sum e autocorrigido min-sum – que trocam complexidade para o desempenho de correção de erros.

A natureza iterativa desses algoritmos significa que a latência da decodificação é diretamente proporcional ao número de iterações e ao tempo de periteração. Arquiteturas paralelas visam reduzir o tempo de periteração, realizando várias atualizações simultaneamente, ou por sobreposições de iterações através da pipelinagem.

Arquiteturas Tradicionais de Decodificação e suas Limitações

Os decodificadores LDPC de hardware iniciais usaram uma abordagem totalmente sequencial: uma única unidade de processamento atualiza cada nó variável por sua vez, e então cada nó de verificação por sua vez, repetindo até a convergência. Esta arquitetura serial requer os recursos de hardware menos mínimos – apenas uma unidade de computação – mas sofre de alta latência e baixo rendimento. Por exemplo, um decodificador que manuseia um comprimento de código de 10.000 bits pode exigir dezenas de microssegundos por iteração, o que é inaceitável para sistemas multi-gigabit modernos.

Outra limitação é a largura de banda da memória. Nas arquiteturas seriais, todas as mensagens intermediárias devem ser armazenadas na memória no chip e acessadas repetidamente. Isto cria um gargalo, uma vez que os tempos de acesso à memória se tornam o fator dominante na duração da iteração. Além disso, o cronograma de atualização sequencial não explora o fato de que muitas atualizações variáveis e de nó de verificação são independentes e podem ser computadas concomitantemente.

A ineficiência dos métodos seriados motivou o desenvolvimento de decodificadores parcialmente e totalmente paralelos. O desafio é aumentar o paralelismo sem causar discórdia de recursos ou violar o cronograma de passagem de mensagens necessário para a convergência.

Arquiteturas de Decodificação Paralelas: Estado da Arte

Os decodificadores LDPC de hardware modernos empregam uma variedade de técnicas paralelas, muitas vezes combinadas. As abordagens mais proeminentes são decodificação em camadas, processamento encapsulado e arquiteturas totalmente paralelas. Cada uma oferece diferentes trocas entre capacidade de transferência, área, potência e correção de erros.

Decodificação em Camadas

A decodificação em camadas reorganiza a matriz de verificação de paridade em camadas - tipicamente linhas ou grupos de linhas - que correspondem a subconjuntos não- sobrepostas de equações de verificação. Dentro de cada camada, todas as atualizações de nós variáveis que tocam nessa camada podem ser processadas simultaneamente, desde que eles não compartilhem o mesmo nó variável. Isto requer um design de matriz cuidadoso para garantir que os pesos das colunas sejam baixos o suficiente para evitar conflitos.

O esquema em camadas acelera drasticamente a convergência. Enquanto um esquema de inundação padrão atualiza todos os nós variáveis, todos os nós de verificação por iteração, o programa em camadas atualiza tanto os nós variáveis quanto os nós de verificação dentro de cada camada em uma única passagem. Isto efetivamente reduz o número de iterações necessárias por um fator de dois ou mais. Por exemplo, um decodificador em camadas pode convergir em iterações de 5-10 onde um decodificador de inundação precisa de 20-30. O resultado é uma redução proporcional na latência.

Os decodificadores de camadas também oferecem benefícios de rendimento intermédio. Uma vez que apenas as mensagens para uma camada devem ser armazenadas de cada vez, os requisitos de memória são menores do que em projetos totalmente paralelos, tornando a decodificação em camadas atraente para a implementação do FPGA, onde o bloco RAM é limitado. Os principais fornecedores de FPGA fornecem núcleos IP que implementam decodificadores LDPC em camadas compatíveis com Wi-Fi, 5G e padrões de satélite.

Exemplo: Um decodificador em camadas para um código (64800, 64800–17280) usado em DVB-S2 pode obter rendimentos superiores a 1 Gbps em FPGAs Xilinx modernos, conforme documentado em este papel IEEE em decodificadores LDPC de alta produtividade .

Processamento de Tubulação

O pipelining é uma técnica de design digital clássica que quebra um cálculo em várias etapas, cada uma completando em um ciclo de relógio, com registros entre as etapas que contêm resultados intermediários. Em decodificadores LDPC, o pipelining pode ser aplicado em vários níveis: dentro de uma única iteração (pipelining de intra-iteração) ou através de múltiplas iterações (pipelining de inter-iteração).

O pipelining intra-iteration divide o cálculo de mensagem para uma variável ou verificar o nó em passos aritméticas menores, como o min-findding, produto-de-sinais e normalização, permitindo que o hardware funcione com uma frequência de relógio mais alta. No entanto, isso aumenta a latência por iteração, que pode compensar o ganho de rendimento se não for cuidadosamente gerenciado.

A pipelinação de inter- iteração é mais agressiva: sobrepõe- se ao processamento da iteração [[FLT: 0]]i com iteração [[FLT: 2]]i+1[[[FLT: 3]]. Isto requer dissociar as memórias da mensagem para que uma possa ser escrita enquanto outra é lida. A profundidade do gasoduto pode ser várias iteraçãos, e deve ser tomado cuidado especial para evitar perigos de dados, onde uma iteração posterior depende de resultados ainda não produzidos. Algumas pesquisas mostraram que técnicas de visão avançada ou horários de atualização modificados podem resolver esses perigos, permitindo um alto grau de paralelismo de inter- iteração.

As arquiteturas pipelined são comumente usadas em implementações ASIC onde o decodificador faz parte de um Sistema-em-Chip maior (SoC). Por exemplo, o decodificador LDPC em um processador de banda base 5G muitas vezes emprega um pipeline de 4-estágios para manter uma taxa de rendimento de 20 Gbps, enquanto se encaixa dentro de um envelope de poder estrito.

Arquiteturas Totalmente Paralelas

O paralelismo é um decodificador totalmente paralelo que atribui uma unidade de processamento dedicada a cada nó variável e a cada nó de verificação no gráfico de Tanner. Todos os nós podem atualizar suas mensagens em um único ciclo de relógio, usando um cronograma de inundação. Isto elimina a sobrecarga sequencial de abordagens em camadas ou encanadas, alcançando o máximo de rendimento possível.

O preço é enorme complexidade de hardware. Um decodificador totalmente paralelo para um código com 10.000 nós variáveis e 5.000 nós de verificação exigiria 15.000 elementos de processamento, além de uma rede de roteamento para conectá- los de acordo com a matriz de verificação de paridade. A fiação domina a área de chip. Historicamente, apenas códigos LDPC muito curtos (com algumas centenas de bits) poderiam ser implementados totalmente em paralelo em um único chip.

No entanto, os avanços na tecnologia ASIC – nós de processo de encolher, integração 3D densa e redes on-chip de alta largura de banda – tornaram os decodificadores totalmente paralelos mais tratáveis. protótipos de pesquisa recentes demonstram decodificadores totalmente paralelos para códigos de comprimento 2000-4000 bits que podem operar em 1-10 Gbps. Estes ainda não são adequados para códigos muito longos (por exemplo, 64k bits para DVB-S2), mas são ideais para aplicações sensíveis à latência, como interconexões ópticas e ligações de satélite de órbita de baixa Terra.

Estudo de caso: Um decodificador LDPC totalmente paralelo para o padrão IEEE 802.11ad (60 GHz WiGig) foi demonstrado em um chip CMOS de 28 nm, atingindo 10 Gbps com 350 mW de potência, conforme descrito em este papel IEEE Journal of Solid-State Circuits .

Outras abordagens notáveis

Várias técnicas adicionais de paralelização merecem menção:

  • Decodificação estocástica: Representa mensagens como sequências de bits aleatórios, permitindo hardware extremamente simples (um único flip-flop por mensagem) ao custo de uma convergência mais lenta. O paralelismo é naturalmente alto porque cada nó opera de forma independente. Decodificadores estocásticos foram explorados para aplicações de muito baixa potência, como dispositivos médicos implantados.
  • Quasi-cíclico (QC) Decodificadores LDPC: A maioria dos padrões modernos usam códigos LDPC quase-cíclicos, onde a matriz de verificação de paridade é composta por submatrices de identidade circularmente deslocadas. Esta estrutura permite ao decodificador usar metamorfos de barril ou redes de permutação para encaminhar mensagens entre elementos de processamento, simplificando grandemente a interconexão. Quase todos os decodificadores em camadas e parcialmente paralelos para códigos QC-LDPC exploram esta regularidade.
  • Arquitecturas paralelas parciais: Um compromisso entre desenhos em camadas e totalmente paralelos, decodificadores paralelos parciais atribuem um número fixo de unidades de processamento para processar múltiplos nós durante vários ciclos de relógio. Ao programar cuidadosamente operações, eles podem alcançar rendimentos próximos a totalmente paralelos, usando significativamente menos área.

Plataformas de Hardware para Implementação de Decodificadores LDPC

A escolha de plataforma – oFPGA, o ASIC ou a GPU – influencia fortemente o paralelismo e os trade-offs de design alcançáveis.

Descodificadores baseados em FPGA

Os FPGAs oferecem reconfigurabilidade, tornando- os populares para prototipagem e para sistemas que devem suportar vários padrões. Os FPGAs modernos contêm milhares de fatias de DSP e RAM de bloco abundante, permitindo decodificadores em camadas com paralelismo moderado. Os decodificadores totalmente paralelos raramente são implementados em FPGAs devido ao congestionamento de roteamento, mas os desenhos parciais paralelos e em camadas podem alcançar a transferência multi- gigabit. A flexibilidade dos FPGAs também permite a adaptação em tempo de execução dos parâmetros de código, o que é valioso para rádios definidos por software.

Descodificadores baseados em ÁSIC

Os circuitos integrados específicos para aplicações (ASICs) são os cavalos de trabalho de chips de comunicações de mercado de massa. Eles podem integrar centenas de elementos de processamento com hierarquias de memória personalizadas e roteamento dedicado. Os decodificadores ASIC para 5G NR e Wi-Fi 6 normalmente excedem 10 Gbps usando arquiteturas em camadas ou encanadas. A eficiência de energia é uma vantagem chave: um decodificador ASIC bem otimizado pode alcançar menos de 1 pJ por bit decodificado.

Descodificadores baseados em GPU

As unidades de processamento de gráficos (GPUs) não são normalmente usadas em receptores de comunicação de produção, mas são valiosas para pesquisa e decodificação offline. Uma GPU moderna pode simular milhares de atualizações de nós em paralelo usando sua arquitetura SIMT (instrução única, múltiplos threads). Pesquisadores usam decodificadores baseados em GPU para testar novos algoritmos e projetos de código sem comprometer com hardware. No entanto, a latência de memória entre CPU e GPU, bem como a sobrecarga de lançamentos de kernel, limita o rendimento para decodificação em tempo real de fluxos de dados de alta taxa.

Desafios em Design de Decodificador Paralelo

Apesar do progresso impressionante, vários obstáculos permanecem antes de decodificadores paralelos LDPC podem atender todos os requisitos de aplicação.

  • Consumo de energia: Unidades de processamento paralelas consomem energia dinâmica significativa. Para dispositivos movidos a bateria, o orçamento de energia pode restringir o grau de paralelismo. Gating de relógio, escala de tensão e computação aproximada são áreas de pesquisa ativa para reduzir a energia sem grandes penalidades de rendimento.
  • Complexidade de hardware: O roteamento e a memória necessários para o alto paralelismo aumentam a área de chip e o esforço de projeto. Para decodificadores totalmente paralelos, a interconexão pode ocupar mais de 70% da área de dados. Arquiteturas hierárquicas e de rede-em-chip estão sendo exploradas para gerenciar complexidade.
  • Floor de erro: Algumas arquiteturas paralelas introduzem efeitos de quantização ou algoritmos simplificados que causam um piso de erro - uma região onde a taxa de erro de bits pára de melhorar conforme a relação sinal-ruído aumenta.Mitigar pisos de erro muitas vezes requer ajuste cuidadoso do algoritmo ou passos pós-processamento que adicionam latência.
  • Scalability: À medida que os comprimentos de código LDPC crescem (para 64k ou 128k bits), manter a concorrência sem conflitos de memória torna-se mais difícil. Decodificadores de camadas exigem que cada camada seja processada sem conflitos; algoritmos de desenho de matriz e de camadas são um campo de pesquisa ativo.

Instruções futuras

A próxima geração de decodificadores LDPC provavelmente combinará paralelismo com novos paradigmas de computação.

  • Decodificação assistida por aprendizado de máquina: As redes neurais podem ser treinadas para aproximar o algoritmo de propagação de crenças, potencialmente reduzindo a contagem de iterações enquanto mantêm o desempenho. Por exemplo, os decodificadores de propagação de crenças neurais usam pesos e deslocamentos aprendidos, e podem ser implementados em hardware com sobrecarga mínima.O desafio é manter adaptabilidade às diferentes condições de canal.
  • Arquiteturas reconfiguráveis e adaptativas: Os futuros decodificadores podem ajustar dinamicamente o seu grau de paralelismo com base nos requisitos de qualidade e rendimento do canal. Por exemplo, um decodificador pode alternar entre modos em camadas e totalmente paralelos em tempo real. Isto requer um tecido de comunicação flexível e lógica de controle de tempo de execução.
  • Integração com correção de erro quântico: À medida que a computação quântica amadurece, a correção de erro para qubits exigirá decodificadores extremamente rápidos - na ordem dos nanosegundos.Decodificadores paralelos LDPC inspirados em projetos clássicos estão sendo avaliados para códigos de superfície e outros códigos de correção de erro quânticos, embora as restrições sejam bastante diferentes (por exemplo, medição de síndrome não destrutiva).
  • 3D integração e interconexões ópticas: A memória de empilhamento morre diretamente em cima de matrizes lógicas pode aliviar os gargalos de largura de banda de memória. Interconexões ópticas no chip poderiam substituir rotas globais de fios em decodificadores totalmente paralelos, reduzindo latência e potência.

Pesquisas mais abrangentes podem ser encontradas em este artigo IEEE Communications Surveys & Tutorials paper on LDPC descodificador arquiteturas e em este artigo ACM Computing Surveys sobre descodificadores LDPC eficientes em termos de energia].

Conclusão

Arquiteturas paralelas de decodificação transformaram códigos LDPC de uma curiosidade teórica em um facilitador prático de comunicação de alta velocidade moderna. Projetos em camadas, pipeados e totalmente paralelos cada um aborda diferentes pontos no espaço de design de rendimento, área e potência. Avanços contínuos na tecnologia de semicondutores e otimização de algoritmos prometem decodificadores ainda mais rápidos e eficientes nos anos que virão. Seja nas estações base de redes 5G, na infraestrutura de transmissão terrestre, ou nos centros de computação de exaescala de amanhã, decodificadores paralelos LDPC permanecerão um componente crítico da infraestrutura global de informação.