UNIVERSIDADE ESTADUAL PAULISTA

"JÚLIO DE MESQUITA FILHO"
CAMPUS DE SÃO JOÃO DA BOA VISTA

VANESSA BEATRIZ MARTÃO

Codificação de canal para redes 5G utilizando códigos polares

São João da Boa Vista
2018



Vanessa Beatriz Martão

Codificação de canal para redes 5G utilizando códigos polares

Trabalho de Graduação apresentado ao Conselho
de Curso de Graduação em Engenharia de Teleco-
municações do Campus de São João da Boa Vista,
Universidade Estatual Paulista, como parte dos re-
quisitos para obtenção do diploma de Graduação
em Engenharia de Telecomunicações .

Orientador: Profao Dra. Cintya Wink de Oliveira
Benedito

São João da Boa Vista
2018



 

 

 

 

 

 

 

 

 

 

 

Martão, Vanessa Beatriz 
 
   Codificação de canal para redes 5G utilizando códigos polares / Vanessa Beatriz Martão. -- São João 
da Boa Vista, 2018.  
   61 p. : il. color. 
 
   Trabalho de Conclusão de Curso – Câmpus Experimental de São João da Boa Vista – Universidade 
Estadual Paulista “Júlio de Mesquita Filho”. 
   Orientador: Profa. Dra. Cintya Wink de Oliveira Benedito 
   Bibliografia 
   1. Códigos de controle de erros (Teoria da informação) 2. Sistemas de comunicação sem fio 3. 
Telecomunicações 4. Teoria da informação 
 

 

CDD 23. ed. – 621.382  

Ficha catalográfica elaborada pela Biblioteca-BJB 
Bibliotecário responsável: João Pedro Alves Cardoso – CRB-8/9717 
 
 
 
 



UNIVERSIDADE ESTADUAL PAULISTA

“JÚLIO DE MESQUITA FILHO”

CÂMPUS EXPERIMENTAL DE SÃO JOÃO DA BOA VISTA

GRADUAÇÃO EM ENGENHARIA DE TELECOMUNICAÇÕES

TRABALHO DE CONCLUSÃO DE CURSO

CODIFICAÇÃO DE CANAL PARA REDES 5G UTILIZANDO CÓDIGOS POLARES

Aluno: Vanessa Beatriz Martão

Orientador: Profª. Drª. Cintya Wink de Oliveira Benedito

Banca Examinadora:

- Profª. Drª. Cintya Wink de Oliveira Benedito 

- Prof. Dr. Carlos Héracles Morais de Lima 

- Prof. Dr. Edgar Eduardo Benitez Olivo

A ata da defesa com as respectivas assinaturas dos membros encontra-se no prontuário do
aluno (Expediente nº 02/2018)

São João da Boa Vista, 08 de fevereiro de 2018



À minha mãe, Sirlei Rafael Martão,
e ao meu pai, Emerson Rogério Martão,

que sempre foram minha maior fonte de inspiração e força,
sou grata por acreditarem e apoiarem meu sonho.

Ao Leonardo Diogo Bueno Bobadilla,
obrigada por ser tão companheiro e pelo incentivo nas hora difíceis.



AGRADECIMENTOS

Agradeço à UNESP, por me proporcionar um ambiente amigável para os estudos. Sou grata à cada
membro do corpo docente, principalmente à professora Cintya Wink de Oliveira Benedito, que fez
toda a diferença nesse ano, por todo apoio, paciência e companheirismo nesses poucos meses de muito
trabalho. Agradeço também à direção e a administração dessa instituição de ensino.



“Não importa o que aconteça, continue a nadar“

(Walters, Graham; Procurando Nemo, 2003)



RESUMO

Códigos Polares são códigos de bloco lineares com baixo custo computacional que tem grande potencial
para serem utilizados na tecnologia 5G, devido a comprovação de que atingem o limite da capacidade
de canal de Shannon. Esses códigos são essencialmente binários, sendo implementados em canais
simétricos e sem memória. O objetivo desse trabalho foi o estudo das estratégias de codificação
e decodificação dos códigos polares visando aplicação nas redes 5G. Para esse fim, fizemos uma
introdução dos elementos da teoria da informação e codificação. Após isto fizemos um estudo da
técnica de polarização do canal que separa os canais bons dos ruins. Foram estudados estratégias
de codificação e decodificação para esses códigos, e feito uma implementação computacional para
verificação de sua eficiência. Os resultados mostraram que conforme o tamanho N da palavra-código
é aumentada, mais próximo do limite dado pelo teorema da capacidade de canal de Shannon os sinais
serão.

PALAVRAS-CHAVE: Teoria da Informação. Códigos Polares. Redes 5G.



ABSTRACT

Polar codes are linear block codes with low computational cost that have great potential to be used
in 5G technology, due to evidence that it achieves the Shannon’s channel capacity. These codes are
essentially binary, being implemented in symmetric and memoryless channels. The objective of this
work was study the coding and decoding strategy of the polar codes for the application in the 5G
networks. To this end, we have introduced the elements of information theory and coding. After that
we did a study about the channel polarization technique that separates the good channels from the bad
ones. We studied coding and decoding strategies for codes, and a computational implementation to
verify its efficiency. The results showed that the larger the N size of the codeword, the closer the signal
is to the limit of the Shannon’s channel capacity theorem.

KEYWORDS: Information Theory. Polar Codes. 5G Networks.



LISTA DE ILUSTRAÇÕES

Figura 1 Entropia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Figura 2 Canal Ideal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Figura 3 Canal Binário Simétrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Figura 4 Canal Binário de Apagamento . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Figura 5 Canal Gaussiano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Figura 6 Código de Bloco Linear. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Figura 7 Polarização de Canal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Figura 8 WN : N cópias do canal W . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Figura 9 Canal Binário Simétrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Figura 10 Canal Binário de Apagamento . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figura 11 Canal W. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figura 12 Construção do Canal W2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figura 13 Construção de W4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figura 14 Construção do canal W8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Figura 15 Construção de WN a partir de duas cópias de WN/2 . . . . . . . . . . . . . . . 36
Figura 16 I(W1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Figura 17 I(W2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Figura 18 I(W4). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Figura 19 I(W8). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Figura 20 Gráfico canais polarizados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Figura 21 Construção de WN alternativa. . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Figura 22 Circuito para implementação da transformação F⊗3. . . . . . . . . . . . . . . . 48
Figura 23 Codificação u′. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Figura 24 Codificação u′′. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Figura 25 Codificação com N = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Figura 26 Arquitetura Decodificador SC N = 8. . . . . . . . . . . . . . . . . . . . . . . 54
Figura 27 Decodificador SC, N = 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Figura 28 Decodificador SC N = 8 após todos os passos. . . . . . . . . . . . . . . . . . 56
Figura 29 Diagrama de Blocos Codificação/Decodificação. . . . . . . . . . . . . . . . . . 56
Figura 30 Gráfico BER por Eb/No. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Figura 31 Gráfico BLER por Eb/No para diferentes codificações. . . . . . . . . . . . . . 59



LISTA DE ABREVIATURAS E SIGLAS

1G Primeira Geração das Comunicações Móveis

2G Segunda Geração das Comunicações Móveis

3G Terceira Geração das Comunicações Móveis

4G Quarta Geração das Comunicações Móveis

1G Quinta Geração das Comunicações Móveis

Gbps Gigabits por segundo

ITU International Telecommunication Union (União Internacional de Telecomunica-
ções)

GSM Global System for Mobile Communications (Sistema Global para Comunicações
Móveis)

TDMA Time Division Multiple Access (Acesso Múltiplo por Divisão no Tempo)

SMS Short Message Service (Serviço de Mensagens Curtas)

UMTS Universal Mobile Telecomunications System (Sistema Universal de Telecomuni-
cações Móveis)

WiMAX Worldwide Interoperability for Microwave Access (Interoperabilidade Mundial
para Acesso de Micro-Ondas)

LTE-A Long Term Evolution - Advanced (Evolução a longo prazo - Avançada)

3GPP 3rd Generation Partnership Project (Projeto de Parceria de 3a Geração)

eMBB Enhanced Mobile Broadband (Banda Larga Móvel Melhorada)

mMTC massive Machine Type Communications (Conexões Massivas de Comunicação
entre Máquinas)

URLLC Ultra-Reliable Low Latency Communication (Comunicações Ultra Confiáveis e
de Baixa Latência)

LDPC Low-Density Parity-Check Codes (Códigos de Verificação de Erros de Paridade
de Baixa Densidade)

SNR Signal-to-Noise Ratio (Relação Sinal-Ruído)

BER Bit Error Rate (Taxa de Erro de Bit)



BSC Binnary Simmetric Channel (Canal Binário Simétrico)

BEC Binary Erasure Channel (Canal Binário com Apagamento)

AWGN Additive White Gaussian Noise (Ruído Gaussiano Aditivo Branco)

V.A. Variável Aleatória

SC Successive Cancellation (Cancelamento Sucessivo)

WCDMA Wide-Band Code-Division Multiple Access (Acesso Múltiplo por Divisão de
Código de Banda Larga)

BP Belief Propagation (Propagação de Crenças)

CRC Cyclic Redundancy Check (Verificação de redundância Cíclica)

CA-SCL Cyclic Redundancy Check Successive Cancellation List (Verificação de Redun-
dância Cíclica na Lista de Cancelamento Sucessivo)

aCA-SCL Cyclic Redundancy Check aided Successive Cancellation List (Verificação de
Redundância Cíclica Auxiliar na Lista de Cancelamento Sucessivo)



SUMÁRIO

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 REVISÃO DE CONCEITOS . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1 Teoria da Informação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Capacidade do canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Códigos de bloco lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 POLARIZAÇÃO DE CANAL . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1 Conceitos Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Combinação de Canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Divisão de Canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Exemplo de Polarização de Canal para BEC . . . . . . . . . . . . . . . . . . . . 38

4 CODIGOS POLARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1 Codificação dos Códigos Polares . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.1 Expressões Algébricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1.2 Exemplo Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Decodificação dos Códigos Polares por SC . . . . . . . . . . . . . . . . . . . . . 51
4.2.1 Decodificador de tamanho 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2 Decodificador de tamanho N . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.3 Passos para decodificação SC . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.4 Exemplo decodificação SC para N=8 . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Implementação Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61



12

1 INTRODUÇÃO

Durante as décadas de 1970 e 1980 foi desenvolvida e colocada em uso a primeira geração das
comunicações móveis (1G), tais sistemas essencialmente analógicos, foram projetados para trafegar
somente voz e tinham como principais desvantagens interfaces não padronizadas, baixa capacidade,
baixa qualidade nas ligações e baixa segurança na transmissão das informações. (KUMAR; RAO,
2015). Da necessidade de atender à crescente demanda pelo serviço móvel, surgiu em seguida a
segunda geração das comunicações móveis (2G), baseado na tecnologia GSM (Global System for

Mobile Communications), entrando em atividade no início da década de 1990 e sendo responsável pela
digitalização da telefonia móvel combinado com a tecnologia de acesso múltiplo por divisão no tempo
(Time Division Multiple Access, TDMA) permitindo os serviços de troca de mensagens de texto curtas
(Short Message Service, SMS), essa tecnologia também foi responsável pela padronização na telefonia
móvel.

Os avanços tecnológicos culminaram na terceira geração das comunicações móveis (3G) em
meados de 2001, proporcionando a primeira grande experiência de banda larga móvel e tendo como
tecnologia padrão principal o UMTS (Universal Mobile Telecomunications System) e provendo diversas
vantagens em comparação a seus antecessores, possuindo cobertura com qualidade superior, maior
velocidade de trafego de dados, suporte a aplicações multimídia e maior imunidade a interferências. A
quarta geração das comunicações móveis (4G) foi implementada comercialmente por volta de 2010,
tendo como tecnologias padrões o WiMAX (Worldwide Interoperability for Microwave Access) e o
LTE-A (Long Term Evolution - Advanced), sendo esta segunda a adotada no Brasil e oferecendo um
serviço de fácil compatibilidade com redes utilizadas anteriormente, maior velocidade, maior largura
de banda, menor latência, melhor cobertura e maior qualidade de rede em comparação às gerações
anteriores. É previsto a implementação da quinta geração (5G) da telefonia móvel a partir de 2020
(SHAFI et al., 2017), essa nova geração necessitará de novas tecnologias para atender a alta demanda
de dispositivos utilizando a rede, pois com a internet das coisas (Internet of Things, IoT), haverá um
crescimento exponencial na utilização de dados e um grande aumento em dispositivos que utilizarão
essa rede.

No ano de 2016 a empresa chinesa Huawei conseguiu uma velocidade de download de 27 Gbps
(Gigabits por segundo) utilizando os códigos polares em uma simulação do 5G (HUAWEI, 2016). Nessa
simulação foi demonstrado que a tecnologia dos códigos polares é capaz de atingir simultaneamente
os três casos típicos definidos como padrão do 5G pela ITU (International Telecommunication Union)
como eMBB (Enhanced Mobile Broadband) acima de 20 Gbps, uRLLC (Ultra-Reliable Low Latency

Communication) com latência de 1 ms e mMTC (massive Machine Type Communications) com bilhões
de conexões. Nesse mesmo ano, 3GPP (3rd Generation Partnership Project) padronizou os códigos
polares como código dominante para controle das funções de canal no cenário eMBB e é possível que
os códigos polares possam atuar nos cenários mMTC e URLLC também pois ainda está em decisão
sobre qual irão adotar (ISCAN; LENTNER; XU, 2016). Códigos turbo não poderão ser utilizados
nesses cenários pois para uma comunicação confiável não é aceitável possuir um patamar de ruído,



13

no qual os códigos turbo possuem. Códigos LDPC (Low-Density Parity-Check Codes) têm uma
performance inferior para comprimentos de blocos menores que 400 bits e para taxas de códigos
menores que 1/3, que são as características para URLLC e mMTC (SHARMA; SALIM, 2017).

Códigos Polares são tidos como promissores para os casos URLLC e mMTC, pois oferecem uma
excelente performance com variedade nas taxas de códigos e comprimentos de códigos por meio de
simples puncionamentos e encurtamento de código, respectivamente (WANG; LIU, 2014). Devido à
ausência de chão de erro, códigos polares podem suportar 99,999% de confiabilidade, que é necessário
para requerimentos de aplicações ultra confiáveis. Usando uma simples codificação e um algoritmo de
decodificação baseado em cancelamento sucessivo diminui o consumo de energia em 20 vezes que os
códigos turbo, para uma mesma complexidade (ISCAN; LENTNER; XU, 2016). Portanto aumentando
a vida útil de baterias para aplicações na internet das coisas, que necessitam de um consumo muito
baixo de energia. Além disso, códigos polares tem menores requerimentos de SNR (Signal-to-Noise

Ratio) do que os outros para taxas de códigos equivalentes, sendo assim provê alto ganho de codificação
e um aumento na eficiência espectral. Esses códigos podem atingir altas taxas de transferência e taxa
de erro de bit (Bit Error Rate, BER) melhorada em relação à tecnologias anteriores e com todas essas
características os códigos polares são atrativos para muitos cenários no 5G (HUAWEI, 2016).

A Codificação Polar é um tipo de codificação que foi desenvolvida em 2009 pelo professor de
Engenharia Elétrica e Eletrônica, Erdal Arikan (ARIKAN, 2009), essa codificação é a primeira no
qual foi comprovado que atinge a capacidade simétrica em canais binários discretos e sem memória
(Binary-Input Discrete Memoryless Channel, B-DMC), essa capacidade atingida é conhecida como
capacidade de Shannon (SHANNON, 1948). Isso é um grande feito, dado que essa codificação possui
um baixo custo computacional para codificação e decodificação. Sua principal estratégia é fazer uma
polarização do canal com o intuito de transmitir bits de informação em canais sem ruido e bits fixos
(congelados) em canais ruidosos.

O objetivo central deste trabalho é a apresentação de estratégias de codificação e decodificação
de códigos polares utilizando a técnica de polarização de canal. Para a codificação será feita uma
construção indutiva utilizando a combinação de canais que será apresentada na polarização de canal e
também através de expressões algébricas utilizando o produto de Kronecker de matrizes. A estratégia
de decodificação será dada utilizando a técnica de cancelamento de sucessivo (successive cancellation,
SC). Uma simulação computacional das estratégias de codificação e decodificação também serão
apresentadas neste trabalho.

Nesse trabalho serão abordados os seguintes assuntos: o Capítulo 2 fará uma breve revisão de
conceitos referentes à teoria da informação e codificação, com foco nos códigos de bloco lineares,
estes sendo necessários para o entendimento da codificação utilizada no trabalho. No Capítulo 3 será
abordada a técnica de polarização do canal, exemplificando sua implementação para canais binários
com apagamento. O Capítulo 4 terá seu foco nas técnicas de codificação e decodificação do canal,
explicando equações, operações com matrizes utilizadas na codificação e demonstrando as equações
necessárias para a implementação da decodificação, exemplificando como esta será feita. Ainda no
Capítulo 4, será apresentada a demonstração de resultados referentes à simulação computacional
realizada. E por fim, no Capítulo 5, será feita uma breve conclusão desse trabalho.



14

2 REVISÃO DE CONCEITOS

Este capítulo será dedicado ao estudo de conceitos básicos da teoria da informação e codificação,
que serão necessários para o desenvolvimento do trabalho. Na Seção 2.1 apresentamos os conceitos de
entropia e informação mútua para podermos definir a capacidade de um canal, e exemplificamos estes
conceitos através de alguns canais importantes como o canal binário simétrico (BSC), o canal binário
com apagamento (BEC) e o canal gaussiano (AWGN). Já na Seção 2.2, focamos no estudo dos códigos
de bloco lineares, iniciando com algumas definições básicas matemáticas como definição de corpo, de
espaço vetorial e corpo finito. Feito isso, apresentaremos o peso de Hamming, matriz geradora e um
breve exemplo de aplicação desses conhecimentos em um código de Hamming. Para um estudo mais
aprofundado recomenda-se a leitura da bibliografia : (HAYKIN, 2001), (COVER, 2012), (RYAN; LIN,
2009) e (HEFEZ, 2008).

2.1 TEORIA DA INFORMAÇÃO

O estudo da teoria da informação envolve os limites fundamentais no desempenho de um sistema
de comunicação, através da especificação do número mínimo de bits por símbolo necessário para
representar completamente a fonte, e da especificação da taxa máxima, chamada capacidade do canal,
à qual a transmissão de informação pode ocorrer através do canal.

De forma mais precisa, informação é a quantificação da incerteza de um processo em termos proba-
bilísticos, essa incerteza é uma surpresa na ocorrência de um evento inesperado, sendo assim gerando
informação. Matematicamente, um evento x = xk com probabilidade p(xk) tem a quantificação da
informação relacionada com o inverso da probabilidade de ocorrência.

Definição 2.1.1 Definimos a quantidade de informação obtida após observarmos um evento x = xk

com probabilidade p(xk), como a função logarítmica

I[xk] = log2

[
1

p(xk)

]
= − log2 p(xk). (2.1)

A média desta medida de informação é dada por:

E[I(xk)] = −
k∑

i=1

p(xi) log2[p(xi)]. (2.2)

Sendo esta a medida de informação média por símbolo. Assim, podemos definir a entropia como esta
informação média associada às observações relativas à variável aleatória (V.A.), ou seja, a entropia é
uma medida de incerteza média associada à variável.

Definição 2.1.2 Seja X uma fonte discreta e sem memória, com função massa de probabilidade:

p(x) = P [X = x]. (2.3)



15

A Entropia de X é definida por:

H(X) = −
∑

p(x) log[p(x)]. (2.4)

Exemplo 2.1.1 Com uma V.A. assumindo dois valores: x = a e x = b. Para P [x = a] = p e

P [x = b] = 1− p o valor de entropia será de:

H(p) = −p log2(p)− (1− p) log2(1− p). (2.5)

Para valores de p=0,5, ou seja, que cada valor possua a mesma probabilidade de ocorrência do

outro, H(x) = 1bit, sendo assim a informação média de observação será 1 bit, como ilustra a figura

Figura 1.

Figura 1 – Entropia.

fonte: Própria autora.

No entanto, para valores de p diferentes, por exemplo p = 0, 7, H(x) = 0, 8813 bit a informação

obtida será menor. O fato de um valor ser mais provável que o outro não acarretará em tanta surpresa

e então a entropia será cada vez menor. Quanto mais uma probabilidade se aproxima de 1, mais

próximo de 0 será a sua entropia.

Informação mútua é uma indicação de quanto a incerteza associada a uma variável se reduziu, por
meio de informações trazidas por outra variável.

Definição 2.1.3 Sejam X e Y variáveis aleatórias, a informação mútua associada a esse par de

variáveis é dada por:

I(X, Y ) =
∑
x

∑
y

p(x, y) log2

[
p(x, y)

p(x)p(y)

]
. (2.6)

Por meio de simplificações obtém-se:

I(X, Y ) = H(X)−H(X/Y ) = H(Y )−H(Y/X). (2.7)



16

As variáveis X e Y precisam ser estatisticamente independentes entre si para haver a redução na
incerteza. Para essas variáveis temos que p(x, y) = p(x)p(y) sendo quantizado o grau de dependência
estatística entre as variáveis.

É possível a utilização da informação mútua entre a entrada e a saída de um canal para avaliar
quão eficiente será o envio dessas mensagens. Caso as informações recebidas sejam independentes
das enviadas é possível notar que esse canal é totalmente destrutivo, sendo a informação mútua nula.
Porém, se as informações recebidas forem fortemente dependentes das enviadas é possível estabelecer
uma conexão.

Definição 2.1.4 Para variáveis aleatórias contínuas a entropia diferencial será definida, podendo

assumir valores negativos, pela seguinte fórmula:

H(X) = −
∫
x

p(x) ln[p(x)]dx. (2.8)

A Informação mútua é análoga:

I(X, Y ) =

∫∫
x,y

p(x, y) · ln
[
p(x, y)

p(x)p(y)

]
dxdy. (2.9)

2.1.1 Capacidade do canal

Essa grandeza utiliza-se da informação mútua para indicar a condição de maior dependência (melhor
fluxo de informação) entre transmissor e receptor, ou seja, é a quantidade máxima de informação capaz
de ser transmitida. Para isso manipula-se as probabilidades de envio.

A capacidade do canal C é dada por:

C = max
p(x)

I(X, Y ). (2.10)

A capacidade do canal é medida em bits por utilização do canal.
A seguir veremos alguns exemplos importantes de canais apresentando o cálculo de suas capacida-

des.

Exemplo 2.1.2 Para um canal ideal, no qual não possua erros.

Figura 2 – Canal Ideal.

fonte: Própria autora.



17

Para esse canal P (Y = 1|X = 1) = P (Y = 0|X = 0) = 1 e P (Y = 0|X = 1) = P (Y =

1|X = 0) = 0, como o canal não gera erros, P (X = 1) = P (X = 0) = 0, 5, com isso é possível

obter 1 bit de informação enviado, sendo essa a capacidade do canal.

Exemplo 2.1.3 O Canal Binário Simétrico (BSC), possui esse nome devido à probabilidade p de

receber um bit 1 supondo que foi transmitido 0 ser igual à probabilidade de receber um bit 0 supondo

a transmissão de um bit 1. A Figura 3 exemplifica esse canal.

Figura 3 – Canal Binário Simétrico.

fonte: Própria autora.

Para esse canal P (Y = 1|X = 1) = P (Y = 0|X = 0) = 1 − p e P (Y = 0|X = 1) = P (Y =

1/X = 0) = p. A capacidade desse canal é C = 1 − H(p), com H(p) é a entropia de uma V.A.

binária dada no exemplo 2.1.1.

Caso a probabilidade p seja 0, o canal se torna ideal, porém se p for correspondente a 0,5 a

capacidade será nula, pois haverá uma incerteza sobre qual bit será transmitido e qual será recebido,

nesse caso toda informação transmitida será destruída.

Exemplo 2.1.4 Um Canal Binário de Apagamento (Binary Erasure Channel, BEC) possui esse nome

devido a sua condição de que, apesar de um canal de entrada X ter a possibilidade de enviar apenas

dois tipos de informações diferentes, sendo estas bits 0 ou 1, durante a recepção, para um canal de

saída Y existe a probabilidade de ele receber três tipos de informações diferentes, sendo estas bits 0,

bits 1 ou então um alerta, representado como o símbolo ?, informando que não foi recebido nenhum

bit, ou seja, o bit foi apagado durante a sua propagação no canal.

Portanto, nesse canal a entrada X é correspondente à {0, 1} e a saída Y a {0, 1, ?}, onde ?

corresponde à condição de apagamento no qual não foi recebido um símbolo valido.

Figura 4 – Canal Binário de Apagamento

fonte: Própria autora.

As probabilidades desse canal são:



18

P (Y = 1|X = 1) = P (Y = 0|X = 0) = 1− p e P (Y =?|X = 0) = P (Y =?|X = 1) = p

A probabilidade p corresponde à probabilidade de ocorrer um apagamento no canal.

O canal BEC é considerado um canal livre de erros, pois ao receber um bit 0 ou 1 tem se a certeza

de que esses foram os bits enviados.

A capacidade desse canal é C = R(1− p), sendo R a taxa de bits de entrada, nessa capacidade

tem-se a certeza de que os bits enviados estão corretos.

Exemplo 2.1.5 Para um Canal Gaussiano, X(t) é um processo estocástico ergódico de média zero

e limitado em banda, a sua amostragem uniforme X(t), i = 1, ..., k gera uma V.A contínua Xi com

amostras transmitidas em t segundos por meio de um canal ruidoso.

A saída desse canal corresponde a Yi e possui um ruído aditivo gaussiano branco (Additive White

Gaussian Noise, AWGN) com média 0 e variância N , Zi e N . Portanto,

Yi = Xi + Zi.

Zi ∼ N (0, N).

Este canal é designado como gaussiano discreto no tempo e sem memória, com o ruído Zi

independente da entrada Xi

Figura 5 – Canal Gaussiano.

fonte: Própria autora.

Para valores de ruído iguais à zero o sinal de saída é igual ao da entrada, portanto o canal pode

transmitir um número real arbitrário sem erro e também a capacidade desse canal é infinita.

Para ruído diferente de zero, porém sem restrições na entrada e com entradas arbitrariamente

distantes de modo que a saída consegue distingui-las com uma pequena probabilidade de erro, diz-se

que a capacidade do canal também é infinita.

Já para canais com variância do ruído diferente de zero e restrição de potencia, obtém-se :

E[X2] 6 P,

σ2 = N.

Como a entrada do canal e do ruído são independentes, tem-se portanto:

E[Y 2] = E[X2] + E[Z2] 6 P +N.



19

A capacidade de informação desses canais gaussianos, é:

C = max I(X, Y )

=
1

2
log

(
1 +

P

N

)
.

Sendo que, para um canal limitado em banda B, esta capacidade é:

C = Blog

(
1 +

P

N

)
,

Onde, P/N é a razão sinal-ruído geralmente expressa em dB, com P e N correspondentes à Watts

ou volts2. B é a banda em Hertz e C é a capacidade do canal em bits/segundo.

2.2 CÓDIGOS DE BLOCO LINEARES

Nesta seção serão apresentados alguns conceitos de códigos de bloco lineares, pois como veremos
no Capítulo 4 um código polar é um código de bloco linear. Para isso será preciso apresentar algumas
definições dadas a seguir.

Definição 2.2.1 Um corpo F é um conjunto que possui duas operações: adição "+"e multiplicação

"."satisfazendo as condições:

1. Associativa:

(a+ b) + c = a(b+ c).

a(bc) = (ab)c.

2. Comutativa:

a+ b = b+ a.

ab = ba.

3. Elemento neutro:

Existe 0 tal que a+ 0 = a = 0 + a,

existe também 1 tal que a · 1 = 1 · a = a.

4. Distributiva:

a(b+ c) = ab+ ac.

(a+ b)c = ac+ bc.

5. Elemento imerso:

Existe −a tal que a+ (−a) = 0,

existe também a−1 tal que a · a−1 = 1, a 6= 0.



20

Exemplo 2.2.1 Números racionais Q, números reais R e números complexos C são exemplos de

corpos. Já o conjunto de números inteiros Z não é um corpo, pois não possui inverso multiplicativo.

Um corpo com uma quantidade finita de elementos é chamado de corpo finito. Esses corpos serão
utilizados na construção de códigos.

Exemplo 2.2.2 Para um número primo p. O conjunto Zp = {0, 1, ..., p− 1} forma um corpo finito.

• Z2 = {0, 1}.

• Z3 = {0, 1, 2}.

Definição 2.2.2 Seja F um corpo e seja V um conjunto com as operações:

+ : V x V −→ V

· : F x V −→ V

V é chamado de espaço vetorial sobre F se as operações satisfazem:

1. (u+ v) + w = u+ (v + u), ∀ v ∈ V .

2. Existe 0 e V tal que:

v + 0 = 0 + v = v, ∀ v ∈ V .

3. u+ v = v + u, ∀ u, v ∈ V

4. Para cada v ∈ V existe v′ tal que:

v + v′ = 0 = v′ + v.

5. a, b ∈ F e v ∈ V , então:

a(bv) = (ab)v.

6. Existe 1 ∈ F tal que:

1 · v = v · 1 = v, ∀ v ∈ V .

7. a · (v + u) = av + au, ∀ a ∈ F e u, v ∈ V .

8. (a+ b)v = av + bv, ∀ a, b ∈ F e v ∈ V .

Exemplo 2.2.3 V = R2 é um espaço vetorial sobre o corpo R:

R2 = {(x, y);x, y ∈ R}

Com as seguintes operações:

• (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2).

• α(x, y) = (αx, αy).



21

Esse exemplo satisfaz as oito condições.

Exemplo 2.2.4 F n
q é um espaço vetorial obre o corpo finito Fq (conjunto de todas as n-uplas de

elementos de Fq). Se x, y ∈ Fq, então para x = (x1, x2, ..., xn), y = (y1, y2, ..., yn).

A partir dessas relações, as operações são:

• x+ y = (x1, x2, ..., xn) + (y1, y2, ..., yn) = (x1 + y1, ..., xn + yn).

• αx = α(x1, ..., xn) = (αx1, ..., αxn), α ∈ Fq.

Definição 2.2.3 Seja Fq um corpo finito com q elementos. Dizemos que C é um código de bloco linear,

de comprimento n e dimensão k sobre Fq se C for um subespaço vetorial com dimensão k de F n
q .

Um código de bloco linear C pode ser caracterizado pelos parâmetros (n, k); Para valores de v ∈ C,
v é uma palavra-código de C; Caso C seja um código sobre Fq, este será considerado alfabeto do código
C; para valores de q = 2 esse código será binário; Para valores de q = esse código será ternário e a
quantidade de palavras-código de um código C = (n, k) sobre Fq é qk.

Exemplo 2.2.5 ParaF 3
2 obtém-se um código de bloco linear C = (000, 001, 010, 011, 100, 101, 110, 111),

com parâmetros (n, k) iguais a (3, 2).

Definição 2.2.4 Denomina-se taxa de código a razão R = k
n

, que é interpretada como o número

médio de bits de informação.

O código (n, k) é denominado código de bloco pois na codificação utiliza-se uma sequência de
k bits no qual serão adicionados n− k bits de redundância gerando uma nova palavra com n bits de
comprimento, sendo n > k. Esses códigos de bloco são ilustrados na Figura 6.

Figura 6 – Código de Bloco Linear.

fonte: Própria autora.

Definição 2.2.5 Dados dois vetores u e v, a distância de Hamming d denotada como d(u, v) é obtida

por meio do número de coordenadas que cada vetor possui diferente do outro.

Exemplo 2.2.6 d(001, 111) = 2

d(000, 111) = 3

Propriedades:



22

1. d(u, v) > 0;

2. d(u, v) = d(v, u);

3. d(u, v) 6 d(u,w) + d(w, v).

Definição 2.2.6 Para códigos de bloco C a distância mínima de Hamming é caracterizada como:

dH(C) = min{d(u, v)|u, v ∈ C/u 6= v}. (2.11)

Para um código C = {0000, 0110, 1001, 1111}, as distâncias de Hamming entre cada um dos
vetores é:

dH (0000, 0110) = 2

dH (0000, 1001) = 2

dH (0000, 1111) = 4

dH (0110, 1001) = 4

dH (0110, 1111) = 2

dH (1001, 1111) = 2

Ou seja,
dH = min{dH(u, v) | u, v ∈ C} = min{2, 4} = 2.

Portanto, compreende-se que a distância mínima de Hamming de um código C com características
{2, 4} a distância mínima será de 2 bits.

Definição 2.2.7 O peso de Hammming wH(v) de um vetor u é o número de componentes não nulos

contidos no vetor. O peso mínimo de Hamming wH(C) de um código C é equivalente ao menor peso

das palavras-código.

Exemplo 2.2.7 Para o código C utilizado anteriormente. Obtém-se

w (0110) = 2

w (1001) = 2

w (1111) = 4

Sendo assim,

w(C) = min{w(v), v ∈ C, v 6= 0} = 2. (2.12)

Teorema 2.2.1 Para um código C e u, v ∈ C:

1. dH(u, v) = wH(u− v).

2. dH(C) = wH(C).

Para um código de bloco (n, k) com distância mínima de Hamming d, classifica-se C como um
código (n, k, d).



23

Exemplo 2.2.8 Utilizando o código C novamente, n = 4, k = 2 e d = 2. Portanto C é um código de

bloco caracterizado por (4, 2, 2)

Para códigos de bloco nos quais a distância mínima de Hamming for correspondente a d, esse

código poderá corrigir até
[
d−1
2

]
erros e detectar até (d− 1) erros.

Em casos de números binários, é possível obter a distância de Hamming utilizando-se da operação
mod-2 entre ambos os vetores e avaliando o peso do vetor resultante, d(u, v) = w(u

⊕
v).

Exemplo 2.2.9 d(u, v) = w(u
⊕

x) = w(10110
⊕

10101) = w(00011)

d(u, v) = 2

Definição 2.2.8 Seja Fq um corpo finito e C ⊂ F n
q um código de bloco linear com parâmetros (n,k,d)

e qk palavras-código.

Seja β = {v1, ..., vk} uma base de C e considere G a matriz cujas linhas são os vetores vi

= (vi1, ..., vin), i = 1, ..., k, ou seja,

G =


v1

...

vk

 ,=

v11 · · · v1n
... . . . ...

vk1 · · · vkn

 . (2.13)

A matriz G é chamada de matriz geradora de C

Exemplo 2.2.10 A matriz geradora do código C = {0000, 0110, 1001} é:

G =

[
0110

1001

]
.

Matrizes geradoras podem ser um codificador natural , pois é possível a construção de códigos de
bloco as utilizando.

Exemplo 2.2.11 Para um código (n, k)=(5, 3) em F 5
2 com vetores 10011,01001,00111 linearmente

independentes. A matriz geradora será:

G =

1001101001

00111

 . (2.14)

Esse código possui 23 = 8 palavras-código dado em (2.14).

Para construir um código C em F 5
2 utilizando a matriz geradora G se considera uma transformação

linear dada por
f : F 3

2 7−→ F 5
2 .

u 7−→ uG.



24

Sendo F 3
2 = {000, 001, 010, 100, 110, 011, 101, 111}, em F 5

2 o código obtido corresponde a uG.
Por exemplo:

uG = (101)

10101

11010

11111

 = (01010).

Com (101) e (01010) sendo o código fonte e o código de canal, respectivamente.
A decodificação desse código pode ser feita encontrando valores de u no qual uG serão correspon-

dentes ao código gerado.

Exemplo 2.2.12 uG= (10101)

(u1u2u3)

10101

11010

11111

 = (10101).

Fazendo a multiplicação entre as matrizes obtém-se:

u1 + u2 + u3 = 1

u2 + u3 = 0

u1 + u3 = 1

u2 + u3 = 0

u1 + u3 = 1

Portanto, u1 = 1, u2 = 0 e u3 = 0.

E então, (10101) é decodificada em (100).

Nem sempre essa é a melhor maneira de decodificar um canal, uma melhor alternativa à esse
método é utilizar G na sua forma padrão, sendo assim possível a decodificação, apenas observando o
início das palavras.

A forma padrão de uma matriz geradora G de um código C possui a seguinte forma:

G = (Ik|P ). (2.15)

No qual Ik é a a matriz identidade de ordem k e P uma matriz k x (n− k).

Para o caso da matriz G =

10101

11010

11111

, utiliza-se de algumas operações elementares e permutações

em suas colunas para resultar em sua forma padrão.
Após essas ações a matriz G corresponderá a:

G =

000|00
010|10
001|01

 .

Sendo as três primeiras colunas correspondentes à I3 e as duas últimas à P .



25

Definição 2.2.9 Matriz controle de paridade é uma matriz no qual se relaciona com uma mensagem

do código para definir se essa mensagem pertence ou não ao código.

Para uma matriz geradora G = (Ik|P ) com código C com (n, k). A matriz controle de paridade
será H = (−P t|In−k), sendo P t a matriz transposta de P . A operação transposição (t) de uma matriz
é feita trocando as linhas pelas colunas.

A possibilidade de utilização da matriz H para verificar se uma palavra pertence ou não ao código
se dá pelo fato de que a operação de multiplicação entre as matrizes G e H t deverá ser nula,

GH t = (Ik|PKx(N−K))

(
−Pkx(n−k)

I(n−k)

)
= 0.

Portanto, se a palavra-código pertencer ao código, ao efetuar sua multiplicação pela matriz H t o
resultado deverá ser nulo.

Exemplo 2.2.13 Para um código binário (6, 3) com matriz geradora

G =

100|111
010|011
001|010

 .

A matriz controle de paridade será:

H =

100|100
111|010
110|001

 .

Para códigos v = (100111) e v′ = (010101)

Verificação para v:

vH t = (100111)



111

011

010

100

010

001


= (000).

Verificação para v′:

v′H t = (010101)



111

011

010

100

010

001


= (110).



26

Como é possível observar, a palavra v após a verificação se anulou, portanto pertence ao código. Já
a palavra v′ retornou uma resposta não nula, portanto ela não faz parte do código. Um exemplo de
aplicação de códigos de bloco é o código de Hamming.

Exemplo 2.2.14 Código de Hamming.

Um código de Hamming de ordem m sobre F2 com matriz teste de paridade Hm, possui ordem

m x n, com colunas sendo elementos de Fm
2 \ {0} utilizando uma ordem qualquer. Sendo assim,

o comprimento de um código de Hamming de ordem n = 2m − 1 tem dimensão correspondente a

k = n−m = 2m−m−1. Verifica-se que d = 3, pois é visível a existência de três colunas linearmente

dependentes. A matriz abaixo exemplificará numericamente:

H3 =

1011100

1101010

0111001

 .

Essa matriz representa um código de Hamming com m = 3.



27

3 POLARIZAÇÃO DE CANAL

Nesse capítulo será demonstrado como é feita a polarização de um canal, um processo que refere-se
ao fato de que é possível sintetizar N cópias independentes de um canal W discreto e sem memória
com fonte binária (B-DMC: Binary Discrete Memoryless Channel), em um segundo conjunto de
entradas binárias {W (i)

N : 1 ≤ i ≤ N}. Para isso, na Seção 3.1, serão apresentados alguns conceitos
preliminares sobre os canais B-DMC e alguns parâmetros. Esse processo de polarização é feito em duas
etapas: a primeira consiste na combinação de canais que será demonstrada na Seção 3.2 e a segunda
etapa consiste na divisão destes canais separando um canal original em canais buns (sem ruídos) e um
canais ruins (ruidosos), por meio da polarização desses canais, essa etapa será exemplificada na Seção
3.3. Os bits de informação que são os bits nos quais não podem sofrer interferência são enviados pelo
canal sem ruídos, enquanto que os outros bits são fixados em zero e transmitidos pelos canais ruidosos,
esses bits que serão fixados em zero são chamados de bits congelados. Chamamos de polarização o
fato da capacidade do canal I(W) convergir para 0 ou 1 quando N tende ao infinito. Na Seção 3.4 será
apresentado um exemplo de polarização para um canal BEC. Este capítulo está baseado basicamente
nas referências (ARIKAN, 2009) e (NIU et al., 2014).

Figura 7 – Polarização de Canal.

fonte: Própria autora.

3.1 CONCEITOS PRELIMINARES

Seja
W : X → Y



28

um canal B-DMC no qual utiliza-se um alfabeto de entrada X , um alfabeto de saída Y e probabilidades
de transição

W (y|x) = P (Y = y|X = x),

sendo que o alfabeto de entrada será sempre X = {0, 1}, o alfabeto de saída e as probabilidades de
transição serão arbitrários.

Iremos considerar WN como sendo o canal resultante de N cópias do canal W , ou seja,

WN : XN → Y N ,

com probabilidades de transição dada por

WN(yN1 |xN1 ) =
N∏
i=1

W (y1|x1), (3.1)

onde yN1 = (y1, · · · , yN) e xN1 = (x1, · · · , xN). A Figura 8 ilustra o canal resultante WN .

Figura 8 – WN : N cópias do canal W

fonte: Própria autora.

Para um canal B-DMC, W, existem dois parâmetros de interesse primário, a saber, a capacidade do
canal e o parâmetro de Bhattacharyya. Esses parâmetros são utilizados para fazer medidas de taxa e
confiabilidade, respectivamente.

A capacidade do canal I(W ) é a maior taxa que comunicações confiáveis conseguem alcançar por
W , usando entradas de W com frequências iguais, podendo ser calculada por:

I(W ) =
∑
y∈Y

∑
x∈X

1

2
W (y|x) log W (y|x)

1
2
W (y|0) + 1

2
W (y|1)

. (3.2)

Já o parâmetro de Bhattacharyya Z(W ) é o limite superior da probabilidade de decisão de erro
de máxima verossimilhança quando W é utilizado somente para transmitir 0 ou 1. Este parâmetro é



29

definido por:

Z(W ) =
∑
y∈Y

√
W (y|0)W (y|1). (3.3)

Temos que Z(W ) utiliza valores em [0, 1], utilizaremos logarítmos na base 2 e consequentemente
I(W ) irá utilizar valores em [0, 1]. A unidade das taxas de código e capacidade do canal serão bits e a
relação entre estes dois parâmetros é dada na Proposição 3.1.1.

Proposição 3.1.1 (ARIKAN, 2009) Para qualquer B-DMC W, temos que:

I(W ) > log
2

1 + Z(W )
, (3.4)

I(W ) 6
√

1− Z(W )2. (3.5)

Através da Proposição 3.1.1, podemos concluir que:

• I(W ) ' 1 se, e somente se, Z(w) ' 0.

• I(W ) ' 0 se, e somente se, Z(w) ' 1.

A capacidade I(W ) se iguala a capacidade de Shannon quando W é um canal simétrico, isto é, um
canal no qual existe uma permutação π na saída do alfabeto Y tal que:

• π−1 = π

• W (y|1) = W (πy|0) para todo y ∈ Y .

Como exemplos de canais simétricos temos o canal binário simétrico (BSC-Binary Symmetric

Channel) e o canal binário com apagamento (BEC-Binary Erasure Channel) definidos em 2.1.3 e 2.1.4,
os quais relacionamos com a polarização de canal nos exemplos abaixo.

Exemplo 3.1.1 O canal BSC é um B-DMC com Y = {0, 1}.

Figura 9 – Canal Binário Simétrico

fonte: Própria autora.

Temos que

W (0|0) = W (1|1) = 1− p e W (1|0) = W (0|1) = p.



30

Exemplo 3.1.2 O canal BEC é um B-DMC se para cada y ∈ Y , tivermos

W (y|0)W (y|1) = 0 ou W (y|0) = W (y|1),

no segundo caso, y é chamado de símbolo de apagamento e a soma de W (y|0) sobre todos os símbolos

de apagamento y é chamada de probabilidade de apagamento do BEC.

Figura 10 – Canal Binário de Apagamento

fonte: Própria autora.

A seguir veremos como são feitas as etapas de combinação e divisão do canal utilizadas na
polarização do canal.

3.2 COMBINAÇÃO DE CANAL

Nesta etapa, combina-se N cópias de um canal W para produzir o vetor de canal WN : XN → Y N ,
sendo N uma potência de 2, ou seja, N = 2n, n > 0.

A seguir apresenta-se uma construção indutiva do vetor de canal WN que é dado por N cópias do
canal W . A construção indutiva se caracteriza pela demonstração da construção do canal para N=
1, 2, 4, 8 e então a construção para N=2n. Inicialmente, para N = 1, será gerado somente um canal
W = W1 = W 1.

Figura 11 – Canal W.

fonte: Própria autora.

Para N = 2 serão geradas duas cópias de W = W1, obtendo assim o canal W2 : X2 −→ Y 2

descrito na figura abaixo.



31

Figura 12 – Construção do Canal W2.

fonte: Própria autora.

A partir da construção do canal W2 apresentada na Figura 12, as probabilidades de transição do
canal serão obtidas pela combinação das entradas u1 e u2 que geram as saídas y1 e y2, da seguinte
forma:

W2(y1, y2|u1, u2) = W (y1|u1 ⊕ u2)W (y2|u2). (3.6)

Mapeando u21 7→ x21, onde u21 são as entradas de W2 e x21 são as entradas de W 2, observe que esta
construção também pode ser representada pela seguinte matriz:

G2 =

[
1 0

1 1

]
, (3.7)

obtendo assim
x21 = u21G2.

A relação entre as probabilidades de transição de W2 dada em (3.6) e de W 2 dada em (3.1) para
N = 2, é dada por:

W2(y
2
1|u21)

.
Agora, para N = 4, teremos o canal W4 : X4 −→ Y 4 obtido pela combinação de duas cópias

independentes de W2. A construção do canal W4 é apresentada a seguir na Figura 13:



32

Figura 13 – Construção de W4.

fonte: Própria autora.

Assim, as probabilidades de transição serão dadas por:

W4(y
4
1|u41) = W4(y1, y2y3, y4|u1, u2u3, u4) = W2(y

2
1|u1 ⊕ u2, u3 ⊕ u4)W2(y

4
3|u2, u4). (3.8)

Porém, a partir de N = 4 será necessária a utilização de uma operação de permutação para a
combinação dos canais, como podemos observar na Figura 13, onde a operação R4 permuta as entradas
dos canais W2. Essa operação de permutação, que será denotada por RN , irá separar as entradas de
índices pares das ímpares, as entradas ímpares estarão posicionadas anteriormente das pares. Essa
operação utiliza-se de uma matriz de permutação para inverter essas posições. No caso de N = 4,
temos a seguinte permutação das entradas:

s41 = (s1s2s3s4) −→ v41 = (s1s3s2s4),

E assim, a matriz de permutação é dada da seguinte forma

R4 =


1 0 0 0

0 0 1 0

0 1 0 0

0 0 0 1

 . (3.9)

Mapeando u41 7→ x41, onde u41 são as entradas de W4 e x41 são as entradas de W 4, esta construção
também pode ser representada pela seguinte matriz:

G4 =


1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

 , (3.10)



33

obtendo assim
x41 = u41G4.

Tem se a relação
W4(y

4
1|u41) = W 4(y41|u41G4)

entre as probabilidades de transição de W4 dado em (3.8) e de W 4 como em (3.1) para N = 4.
Já para N = 8 gera-se o canal W8 : X

8 −→ Y 8 cuja construção é dada pela figura abaixo.

Figura 14 – Construção do canal W8.

fonte: Própria autora.

Assim, as probabilidade de transição serão dadas por

W8(y
8
1|u81) = W (y41|u1 ⊕ u2, u3 ⊕ u4, u5 ⊕ u6, u7 ⊕ u8)W (y85|u81,e). (3.11)

A operação de permutação R8 irá mapear a entrada da seguinte forma

s81 = (s1s2s3s4s5s6s7s8) 7→ v81 = (s1s3s5s7s2s4s6s8),



34

que pode ser representada pela seguinte matriz

R8 =



1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1


. (3.12)

Mapeando u81 7→ x81, onde u81 são as entradas de W8 e x81 são as entradas de W 8, esta construção
também pode ser representada pela seguinte matriz:

G8 =



1 0 0 0 0 0 0 0

1 0 0 0 1 0 0 0

1 0 1 0 0 0 0 0

1 0 1 0 1 0 1 0

1 1 0 0 0 0 0 0

1 1 0 0 1 1 0 0

1 1 1 1 0 0 0 0

1 1 1 1 1 1 1 1


(3.13)

obtendo assim
x81 = u81G8.

Novamente, tem-se a relação

W8(y
8
1|u81) = W 8(y81|u81G8)

entre as probabilidades de transição de W8 dado em (3.11) e de W 8 como em (3.1) para N = 8.
Para o caso geral, duas cópias independentes de WN/2, sendo N/2 correspondente a metade das

N cópias do canal W que serão combinadas produzindo um canal WN : XN −→ Y N . A construção
deste canal é dada na figura abaixo.



35

Figura 15 – Construção de WN a partir de duas cópias de WN/2

fonte: Própria autora.

Para descrevermos as probabilidades de transição de WN , observe que o vetor de entrada uN1 para
WN é transformado primeiramente em sN1 de tal forma que

s2i−1 = u2i−1 ⊕ u2i e s2i = u2i, para 1 < i < N/2.

Assim, o operador RN age na entrada sN1 produzindo vN1 = (s1s3, ..., sN−1, s2s4, ..., sN) que se
tornarão as entradas para as duas cópias de WN/2.

Prosseguindo por indução, mapeando uN1 7→ xN1 , da entrada do vetor do canal WN para a entrada
do canal WN pode ser representada pela matriz GN tal que

xN1 = uN1 GN , (3.14)

onde, N = 2n, n > 0.

A matriz GN é chamada de matriz geradora de tamanho N . Dessa forma, as probabilidade de



36

transição dos dois canais WN e WN são relacionados por:

WN(y
N
1 |uN1 ) = WN(yN1 |uN1 GN). (3.15)

3.3 DIVISÃO DE CANAL

Nesta etapa de divisão, os canais sintetizados são reagrupados pelo grau de polarização, ou seja,
transformamos novamente WN em um conjunto de N canais com coordenadas binárias

W
(i)
N : X −→ XN ×X i−1, com 1 ≤ i ≤ N,

definido pelas probabilidades de transição

W
(i)
N (yN1 , u

i−1
1 |ui) =

∑
uN
i+1∈XN−I

1

2N−1
WN(y

N
1 |uN1 ),

onde ui denota a entrada e (yN1 , u
i−1
1 ) denota a saída de WN(i).

Por exemplo, para N = 1, escrevemos

(W,W ) 7→ (W
(1)
2 ,W

(2)
2 ),

onde por (3.6), temos que

W
(1)
2 (y21|u1) =

∑
u2

1

2
W2(y

2
1|u21) =

∑
u2

1

2
W (y1|u1 ⊕ u2)W (y2|u2)

e
W

(2)
2 (y21, u1|u2) =

1

2
W2(y

2
1|u21) =

1

2
W (y1|u1 ⊕ u2)W (y2|u2).

Para um valor qualquer de N = 2n, com n ≥ 0 e 1 ≤ i ≤ N , generalizamos da seguinte forma:

(W
(i)
N ,W

(i)
N ) 7→ (W

(2i−1)
2N ,W

(2i)
2N ),

com probabilidades de transição dadas por:

W
(2i−1)
2N (y2N1 , u2i−21 |u2i−1) =

∑
u2i

1

2
W

(i)
N (yN1 , u

2i−2
1,o ⊕ u2i−21,e |u2i−1 ⊕ u2i)W

(i)
N (y2NN+1, u1,e2i−2|u2i)

(3.16)
e

W
(2i)
2N (y2N1 , u2i−11 |u2i) =

1

2
W

(i)
N (yN1 , u

2i−2
1,o ⊕ u2i−21,e |u2i−1 ⊕ u2i)W

(i)
N (y2NN+1, u1,e2i−2|u2i). (3.17)

Os canais {W (i)
N } também serão considerados na Seção 4.2, quando apresentamos a estratégia

de decodificação por cancelamento sucessivo em que o i-ésimo elemento de decisão estima ui após
observar yN1 e as entradas anteriores ui−11 . O efeito da combinação e divisão de canais na polarização



37

de canal é sintetizado no resultado a seguir.

Teorema 3.3.1 (ARIKAN, 2009) Para qualquer canal B-DMC, W, os canais {W (i)
N } polarizam no

sentido que, quando N tende para o infinito, para qualquer δ ∈ (0, 1), a fração de índices i ∈
{1, · · · , N} para os quais I(W (i)

N ) ∈ (1− δ, 1] tende para I(W ) e a fração de índices i ∈ {1, · · · , N}
para os quais I(W (i)

N ) ∈ [0, δ) tende para 1− I(W ).

A polarização de canal pode ser recursivamente implementada transformando múltiplos usos
independentes de um determinado B-DMC em um conjunto de usos sucessivos de canais de entrada
binária sintetizados. Para os cálculos de {I(WN(i))} são utilizadas as Equações (3.16) e (3.17). Porém,
segundo (ARIKAN, 2009), não se tem algoritmos eficientes conhecidos para o cálculo de {I(WN(i))}
para um canal B-DMC, W, geral.

Na próxima seção, exemplificamos os cálculos de {I(WN(i))} para um canal BEC.

3.4 EXEMPLO DE POLARIZAÇÃO DE CANAL PARA BEC

Considere um canal binário com apagamento BEC, ver def. Figura 10, com probabilidade de
transição p = 0, 5. Por (ARIKAN, 2009), os valores {I(WN(i))} podem ser calculados através das
relações recursivas

I(W
(2i−1)
N ) = I(W

(i)
N/2)

2 (3.18)

e
I(W

(2i)
N ) = 2I(W

(i)
N/2)− I(W

(i)
N/2)

2, (3.19)

com I(W
(1)
1 ) = 1− p.

Iniciando com um canal, N = 20, a correspondente capacidade do canal será

I(W ) = 1− p = 0, 5.

Figura 16 – I(W1).

fonte: Própria autora.

Agora, combinando dois canais BEC independentes (W,W ), N = 21, a capacidade deste canal
resultante será

2I(W ) = 2× 0, 5 = 1,

que será dividida entre os dois canais sintetizados, conforme ilustra a Figura 17, os quais denotaremos
como W−, com entrada u1 e saídas y1 e y2 e, como W+ com entrada u2 e saídas u1, y1 e y2.



38

Figura 17 – I(W2).

fonte: Própria autora.

Assim, após a combinação e divisão do canal teremos

I(W−) + I(W+) = 2I(W ) = 1,

com I(W−) ≤ I(W ) ≤ I(W+). Logo, por (3.18) e (3.19), temos que

I(W+) = 2I(W )− I(W )2 = 1− 0, 52 = 0, 75

I(W−) = I(W )2 = 0, 52 = 0, 25.
(3.20)

Prosseguindo com 4 usos independentes do BEC, N = 22, teremos inicialmente as 4 cópias de W
divididas em 2 grupos, e os dois BECs de cada grupo são transformados em canais polarizados W− e
W+. Dessa forma, os canais W−− e W−+ são derivados do canal W− e os canais W+− e W++ são
derivados do canal W+.

Figura 18 – I(W4).

fonte: Própria autora.

A capacidade dos canais serão dadas, utilizando (3.20), por

I(W−−) = I(W−)2 = 0, 252 = 0, 0625

I(W−+) = 2I(W−)− I(W−)2 = 2× 0, 25− 0, 252 = 0, 4375

I(W+−) = I(W+)2 = 0, 752 = 0, 5625

I(W++) = 2I(W+)− I(W+)2 = 2× 0, 75− 0, 752 = 0, 9375

(3.21)

Com 8 usos independentes do BEC, N = 23, dividimos inicialmente em 2 grupos de 4 canais, os
quais cada um dos 2 são divididos em 2 grupos de 2, e os dois de cada grupo são transformados em
dois canais polarizados W− e W+.



39

Figura 19 – I(W8).

fonte: Própria autora.

A capacidade dos canais serão dadas, utilizando (3.21), por

I(W−−−) = I(W−−)2 = 0, 0039

I(W−−+) = 2I(W−−)− I(W−−)2 = 0, 1211

I(W−+−) = I(W−+)2 = 0, 1914

I(W−++) = 2I(W−+)− I(W−+)2 = 0, 6836

I(W+−−) = I(W+−)2 = 0, 3164

I(W+−+) = 2I(W+−)− I(W+−)2 = 0, 8086

I(W++−) = I(W++)2 = 0, 8789

I(W+++) = 2I(W++)− I(W++)2 = 0, 9961

(3.22)

Procedendo com o mesmo raciocínio, a polarização pode ser continuamente realizada para N = 2n

usos independentes do canal BEC, W, e a capacidade destes canais polarizados podem ser calculadas
recursivamente.

Como o comprimento do códigoN tende para o infinito, os canais polarizados vão para os extremos,
que correspondem a 0 e 1.



40

Figura 20 – Gráfico canais polarizados.

fonte: (NIU et al., 2014)

A técnica de polarização de canal, nos auxilia a separar os chamados canais bons dos chamados
canais ruins, ou seja, permite identificar quais entradas serão bits de informação e quais serão bits
congelados. Por exemplo, para construir um código com 8 bits de entrada sendo 4 congelados e 4
livres, analisamos a polarização I(W8) ilustrada na Figura 19 e descrita em 3.22. Assim, as entradas
congeladas serão u1, u2, u3 e u5, e as entradas livres serão u4, u6, u7 e u8.



41

4 CODIGOS POLARES

Esse capítulo tratará sobre a codificação e decodificação dos códigos polares que utilizam o
fenômeno de polarização do canal apresentado no Capítulo 3 para sintetizar o seu funcionamento. Na
Seção 4.1 será apresentada a codificação dos códigos polares utilizando os canais WN apresentados na
Seção 3.2 e também através de expressões algébricas utilizando o produto de Kronecker de matrizes.
Além disso, um exemplo dessa codificação será dado na Subseção 4.1.2. A Seção 4.2 irá demonstrar
como é feita a decodificação por cancelamento sucessivo (successive cancellation, SC) para códigos
polares. Na Subseção 4.2.1 será apresentado um exemplo do decodificador com tamanho 2 para
na Subseção 4.2.2 ser apresentado o decodificador com tamanho N , contendo passo-a-passo desse
processo de decodificação. A Subseção 4.2.3 exemplificará a decodificação passo-a-passo para um
código de tamanho N = 8. Por fim, na Seção 4.3 será demonstrado como foi feita a implementação
computacional de códigos polares para verificar sua codificação e decodificação gerando curvas para
diferentes valores de N da BER pela relação sinal ruído. Foram utilizados para o desenvolvimento
desse capítulo os seguinte artigos: (ARIKAN, 2009), (WASSERMAN, 2014), (HUILGOL, 2017),
(LAMARE, 2017) e (VANGALA, 2018).

4.1 CODIFICAÇÃO DOS CÓDIGOS POLARES

Nesta seção apresentamos uma estratégia de codificação para os códigos polares através do produto
tensorial de matrizes, o produto de Kronecker. Como veremos, esta estratégia está diretamente
relacionada com a construção dos canais WN apresentadas no Capítulo 3.

Foi visto na Seção 3.14, que para cada N = 2n com n ≥ 0, a codificação de um canal com vetores
de entrada uN1 e vetores de saída xN1 , se caracteriza por:

xN1 = uN1 GN ,

onde GN é a matriz geradora de ordem N . Utilizando a polarização de canal, apresentada no Capítulo
3, para decidir quais serão os bits de informação e quais são os bits congelados, o congelamento dos
bits pode ser feito a partir de uma divisão do vetor uN1 em duas partes. Dividimos uN1 em uA que
indica os vetores livres e uAc que indica os vetores congelados, onde A é um subconjunto arbitrário de
{1, ..., N} .

A codificação ficará da seguinte maneira:

xN1 = uAGN(A)
⊕

uAcGN(Ac), (4.1)

onde GN(A) indica a submatriz que é formada pelas linhas da matriz GN com índices A, o mesmo
ocorre para GN(Ac).

Fixando A e uAc e, deixando uA livre, obtemos um mapeamento do bloco fonte uA de comprimento
K para o bloco palavra-código xN1 de comprimento N . Dessa forma, definimos um código polar,



42

como sendo um código de bloco linear com parâmetros (N,K,A, uAc), ondeK é a dimensão do código
e especifica o tamanho de A.

A seguir apresentamos um exemplo de codificação polar utilizando a Equação 4.1.

Exemplo 4.1.1 Considere um código polar com parâmetros (4, 2, {2, 4}, (1, 0)). Pela Equação 4.1, o

codificador corresponde a:

x41 = u41G4 = (u2, u4) ·

[
1 0 1 0

1 1 1 1

]
⊕ (1, 0) ·

[
1 0 0 0

1 1 0 0

]

Como estamos considerando códigos binários, as entradas livres (u2, u4) podem assumir os valores

(0, 0), (0, 1), (1, 0) e (1, 1). A seguir, descrevemos a palavra código para cada um dos casos.

• Para (u2, u4) = (0, 0):

x41 = (0, 0) ·

[
1 0 1 0

1 1 1 1

]
⊕ (1, 0) ·

[
1 0 0 0

1 1 0 0

]
= (1, 0, 0, 0)

• Para (u2, u4) = (1, 0):

x41 = (1, 0) ·

[
1 0 1 0

1 1 1 1

]
⊕ (1, 0) ·

[
1 0 0 0

1 1 0 0

]
= (0, 0, 1, 0)

• Para (u2, u4) = (0, 1):

x41 = (0, 1) ·

[
1 0 1 0

1 1 1 1

]
⊕ (1, 0) ·

[
1 0 0 0

1 1 0 0

]
= (0, 1, 1, 1)

• Para (u2, u4) = (1, 1):

x41 = (1, 1) ·

[
1 0 1 0

1 1 1 1

]
⊕ (1, 0) ·

[
1 0 0 0

1 1 0 0

]
= (1, 1, 0, 1)



43

4.1.1 Expressões Algébricas

Para um melhor entendimento da codificação serão demonstradas expressões algébricas correspon-
dentes à matriz geradora GN utilizada em códigos polares, essas formas demonstram a eficiência da
implementação da geração de codificação xN1 = uN1 GN .

Iniciamos definindo o produto de Kronecker de matrizes que será utilizado nesta estratégia de
codificação.

Definição 4.1.1 O produto de Kronecker é uma operação entre duas matrizes no qual denota-se pelo

símbolo ⊗. Utilizando-se uma matriz A com dimensões m x n e uma matriz B com dimensões p x q:

A⊗B =


a11B · · · a1nB

... . . . ...

am1B · · · amnB

 (4.2)

Mais especificamente:

A⊗B =



a11b11 a11b12

a11b21 a11b22
· · ·

a1nb11 a1nb12

a1nb21 a1nb22
... . . . ...

am1b11 am1b12

am1b21 am1b22
· · ·

amnb11 amnb12

amnb21 amnb22


(4.3)

Observação 4.1.1 O tamanho da palavra código influenciará fortemente na complexidade da co-

dificação. Para um tamanho de palavra código N sera utilizada uma matriz FN = F⊗n onde se

caracteriza por F⊗n = F ⊗ F⊗(n−1), no qual n > 0.

Exemplo 4.1.2 Seja

F =

[
1 0

1 1

]
(4.4)

A matriz F⊗n varia conforme o produto de Kronecker, portanto para n = 1, F⊗1 = F ⊗ F⊗0:
Por convenção torna-se F⊗0 = [1], então:

F⊗1 = F ⊗ F⊗0

= F ⊗ [1]

=

[
1 0

1 1

]
.

Para n = 2

F⊗2 = F ⊗ F⊗1



44

F⊗2 =


(
1 0

1 1

)
· 1

(
1 0

1 1

)
· 0(

1 0

1 1

)
· 1

(
1 0

1 1

)
· 1



F⊗2 =


1 0 0 0

1 1 0 0

1 0 1 0

1 1 1 1

 .
Para n = 3:

F⊗3 = F ⊗ F⊗2

F⊗3 =



1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 1 1 1 0 0 0 0

1 0 0 0 1 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 1 1 1


.

Considere o canal W2 descrito na Figura 12, iremos denotar a sua matriz geradora dada em (3.7)
por

F = G2 =

[
1 0

1 1

]
. (4.5)

Já para o canalW4 descrito na Figura 13, a matriz geradoraG4 pode ser obtida por meio da seguinte
expressão:

G4 = (I2 ⊗ F )R4(I2 ⊗ F ), (4.6)

onde I2 é a matriz identidade de ordem 2 e R4 é a matriz de permutação dada em (3.9). E, para canal
W8 descrito na Figura 14:

G8 = (I4 ⊗ F )R8(I2 ⊗G4), (4.7)

onde I4 é a matriz identidade de ordem 4 e R8 é a matriz de permutação dada em (3.12). Prosseguindo
de modo análogo, para um canal WN como descrito na Figura 15, a matriz geradora GN será obtida
por:

GN = (IN/2 ⊗ F )RN(I2 ⊗GN/2) (4.8)



45

onde IN/2 é a matriz identidade de ordem N/2 e RN é uma matriz de permutação de ordem N .
A combinação de canal descrita na Figura 15 pode ser modificada de modo que se obtenha uma

combinação como na Figura 21.

Figura 21 – Construção de WN alternativa.

fonte: Própria autora.

Essa modificação algebricamente corresponde a seguinte equação:

(IN/2 ⊗G2)RN = RN(F ⊗ IN/2). (4.9)

Logo, substituindo a relação (4.9) em (4.8) obtém-se:

GN = RN(F ⊗ IN/2)(I2 ⊗GN/2) = RN(F ⊗GN/2) (4.10)

Substituindo GN/2 = RN/2(F ⊗GN/4) em (4.10) e utilizando a identidade

(AC)⊗ (BD) = (A⊗B)(C ⊗D),



46

com A = I2, B = RN/2, C = F e D = F ⊗GN/4 segue que:

GN = RN(F ⊗ (RN/2(F ⊗GN/4))) = RN(I2 ⊗RN/2)(F
⊗2GN/4) (4.11)

Aplicando novamente (4.10), finalmente obtemos que:

GN = BNF
⊗n, (4.12)

onde
BN = RN(I2 ⊗BN/2) = BN = RN(I2 ⊗RN/2)(I4 ⊗RN/4)...(IN/2 ⊗R2) (4.13)

O operador permutação dado pela matriz de permutação RN será chamado operador de embaralha-
mento no qual faz o mapeamento das entradas do canal, trocando suas posições, que como vimos, é
feito por meio do deslocamento das entradas de índices ímpares para as posições iniciais do canal e
logo em seguida as entradas com índices pares são posicionadas, as posições dos índices são deslocadas
em ordem de crescimento.

Já a matriz de permutação BN atua como operador inversor de bits, como é possível observar em
(4.13). Conforme N aumenta, BN fará cada vez mais trocas nas posições dos vetores.

Para o valor N = 4, B4 = R4 dado em (3.9). Já para N = 8, considerando R8 como em (3.12),
segue que:

B8 = R8(I2 ⊗B4)

=



1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1


·



1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1



=



1 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 1


Definição 4.1.2 Para estimar a complexidade da codificação, será utilizado um modelo computacional

que é uma maquina com um único processador com memória de acesso aleatório e as complexidades

serão expressadas no tempo. A discussão será dada para um código de classe lateral GN arbitrário



47

com parâmetros (N ,K,A, uAc).

O pior caso de complexidade de codificação sobre todos (N ,K,A, uAc) com comprimento N de
bloco se classificará por χE(N). Utilizando a complexidade de uma adição mod-2 escalar como uma
unidade e a complexidade da operação de embaralhamento RN como N unidades, é possivel observar
pela Figura 15 que χE(N) 6 N/2 + N + 2χE(N/2). Com um valor inicial χE(2) = 3, obtém-se
que χEN 6 3/2N logN para todos N = 2n, n > 1, sendo assim a complexidade da codificação é
O(N logN).

Uma implementação específica do codificador é ilustrada na Figura 22, nessa imagem utiliza-se
um canal com N = 8.

Figura 22 – Circuito para implementação da transformação F⊗3.

fonte: Própria autora.

Ao fazer uma análise detalhada dos nós do codificador da Figura 22 é possível observar que as
saídas x81 irão corresponder as seguintes entradas de ũ81:

• x1 ←→ ũ1, ũ2, ũ3, ũ4, ũ5, ũ6, ũ7, ũ8;

• x2 ←→ ũ2, ũ4, ũ6, ũ8;

• x3 ←→ ũ3, ũ4, ũ7, ũ8;

• x4 ←→ ũ4, ũ8;

• x5 ←→ ũ5, ũ6, ũ7, ũ8;

• x6 ←→ ũ6, ũ8,

• x7 ←→ ũ8.



48

Este formato do codificador demonstra que para entradas ũ81 as saídas correspondentes serão

x81 = ũ81F
⊗3,

sendo assim o codificador da Figura 22 será equivalente à F⊗3 dada por:

F⊗3 =



1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 1 1 1 0 0 0 0

1 0 0 0 1 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 1 1 1


.

Agora, se analisarmos os nós da Figura 22 utilizando como entradas os valores de u81, que "sofrem"
a operação de reversamento de bit, será equivalente à codificação apresentada na Figura 14. Assim,
a matriz utilizada para codificação será G8 como em (3.13). Portanto, para as entradas u81 as saídas
correspondentes serão:

x81 = u81G8.

Uma alternativa de aplicação do codificador seria a utilização de u81 na ordem natural de entrada do
circuito na Figura 22, obtendo-se

x̃81 = u81F
⊗3

na saída. Sendo assim, a codificação poderia ser completada por uma operação de inversão de bits
após o reversamento de bit, ou seja,

x81 = x̃81B8 = u81G8.

A complexidade dessa implementação é O(N logN) com O(N) para BN e O(N logN) para F⊗n.
Muitas alternativas de implementação para F⊗n podem ser obtidas pelo circuito de codificação

da Figura 22, como por exemplo utilizando N processadores, um faz a implementação "coluna por
coluna" reduzindo então a latência total para logN , várias outras trocas são possíveis entre latência e
complexidade de hardware.

Atualmente códigos polares são implementados utilizando F⊗n no lugar de BNF
⊗n com o mapea-

mento do codificador como intuito de simplificar a implementação. Para esse caso, o decodificador
deve compensar decodificando os elementos do vetor de origem uN1 na ordem indexada de reversa-
mento de bit. Inclui-se assim, BN como parte do codificador nesse projeto para a utilização de um
decodificador que decodifica uN1 na ordem natural de índice, simplificando a notação.



49

4.1.2 Exemplo Codificação

Para N = 8 canais, utilizando a polarização de canal exemplificado na Seção 3.3, podemos utilizar
quatro entradas congeladas e quatro livres, para construir um código polar com os seguintes parâmetros:
(N,K,A, uAc) = (8, 4, {4, 6, 7, 8}, (0, 0, 0, 0)). Neste caso, as entradas livres u4, u6, u7, u8 podem
assumir os valores 0 ou 1.

A seguir vamos exemplificar esta codificação para dois vetores de entrada utilizando a codificação
descrita na Figura 19 .

• Para u′ = (0, 0, 0, 1, 0, 1, 0, 1) temos a seguinte codificação:

Figura 23 – Codificação u′.

fonte: Própria autora.

Logo, a palavra-código é x′ = (1, 1, 0, 0, 0, 0, 1, 1).

• Para u′′ = (0, 0, 0, 1, 0, 0, 1, 0) temos a seguinte codificação:

Figura 24 – Codificação u′′.

fonte: Própria autora.



50

Logo, a palavra-código é x′′ = (0, 1, 0, 1, 1, 0, 1, 0).

Utilizando o circuito descrito na Figura 22, que utiliza da equação x81 = ũ81F
⊗3 para a codificação

do canal, faremos um exemplo para ũ81 = (0, 0, 0, 1, 0, 0, 1, 0). Tem-se que:

x81 = (0, 0, 0, 1, 0, 0, 1, 0) ·



1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 1 1 1 0 0 0 0

1 0 0 0 1 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 1 1 1


.

x81 = (0, 1, 0, 1, 1, 0, 1, 0). (4.14)

Portanto, a palavra-código x81 é (0, 1, 0, 1, 1, 0, 1, 0), que como pode-se observar é igual a palavra-
código x′′.

4.2 DECODIFICAÇÃO DOS CÓDIGOS POLARES POR SC

A decodificação de códigos polares é feita a partir de um decodificador de cancelamento sucessivo
(successive cancellation decoder, SCD). Nessa técnica, o decodificador geralmente dispõe somente
das informações sobre os valores e posições dos bits congelados, uAc e A respectivamente, e conforme
é feita a decodificação do sinal estima-se ûN1 referente aos vetores uN1 . A razão de verossimilhança
(Likelihood Ratio, LR) é obtida pela equação:

L
(i)
N (yN1 , u

i−1
1 ) =

W i
N(y

N
1 , u

i−1
1 |ui = 0)

W i
N(y

N
1 , u

i−1
1 |ui = 1)

. (4.15)

4.2.1 Decodificador de tamanho 2

Para um decodificador com tamanho N = 2. A Figura 25 demonstra como sua entrada é construída,
o codificador mapeia uN1 para xN1 que serão transmitidos através do canal W e serão recebidos vetores
yN1 .

Figura 25 – Codificação com N = 2.

fonte: Própria autora.



51

Com essa arquitetura de canal, G2 é seu próprio inverso, ou seja x1 = u1 ⊕ u2, x2 = u2 equivale a
u1 = x1 ⊕ x2, u2 = x2

Para qualquer y recebido, as transições de probabilidades são W (y|x = 0) e W (y|x = 1). Fixando
a = W (y1|x1 = 0), b = W (y1|x1 = 1), c = W (y2|x2 = 0), d = W (y2|x2 = 1). Somente os dados
a, b, c, d são necessários, descartando a necessidade de y1 e y2

A decodificação de u1 é feita a partir da computação e comparação das probabilidadesW (y1, y2|u1 =
0) e W (y1, y2|u1 = 1). Os vetores yN1 também dependem de u2, que possui uma probabilidade equiva-
lente de ser tanto 0 quanto 1. Então

W (y1, y2|u1 = 0) = W (y1, y2|u1 = 0, u2 = 0)/2 +W (y1, y2|u1 = 0, u2 = 1)/2

= W (y1, y2|x1 = 0, x2 = 0)/2 +W (y1, y2|x1 = 1, x2 = 1)/2.

Com transições x1 → y1 e x2 → y2 independentes, pode-se avaliar as probabilidades emparelhadas:

W (y1, y2|u1 = 0) = W (y1|x1 = 0)W (y2|x2 = 0)/2 +W (y1|x1 = 1)W (y2|x2 = 1)/2

= (ac+ bd)/2.

Da mesma forma,

W (y1, y2|u1 = 1) = W (y1, y2|u1 = 1, u2 = 0)/2 +W (y1, y2|u1 = 1, u2 = 1)/2

= W (y1, y2|x1 = 1, x2 = 0)/2 +W (y1, y2|x1 = 0, x2 = 1)/2

= W (y1|x1 = 1)W (y2|x2 = 0)/2 +W (y1|x1 = 0)W (y2|x2 = 1)/2

= (bc+ ad)/2.

A razão dessas probabilidades é (ac+ bd)/(bc+ ad). Dividindo numerador e denominador por bd
obtém-se:

a
b
c
d
+ 1

c
d
+ a

b

.

Essa é a razão de verossimilhança de u1 com y1 e y2 dados, podendo ser expressada em termos de
a/b e c/d que são as LRs de x1 e x2.

Define-se a função:

f(p, q) =
pq + 1

p+ q
. (4.16)

O valor de û1 é escolhido de acordo com a seguinte relação:

û1 =

{
0, se f(a/b, c/d) > 1

1, caso contrário.

A decodificação de u2 é feita a partir da determinação de qual valor de u2 possui maior probabilidade



52

de produzir y1 e y2. É feito o cálculo de LR de W (y1, y2|u2 = 0)/W (y1, y2|u2 = 1). De acordo
com regra de cancelamento sucessivo, assumindo que a decodificação de u1 foi feita corretamente, se
u1 = 0, LR será:

W (y1, y2|u1 = 0, u2 = 0)

W (y1, y2|u1 = 0, u2 = 1)
=

W (y1, y2|x1 = 0, x2 = 0)

W (y1, y2|x1 = 1, x2 = 1)

= ac/bd

= (a/b)(c/d).

E para u1 = 1, LR será

W (y1, y2|u1 = 1, u2 = 0)

W (y1, y2|u1 = 1, u2 = 1)
=

W (y1, y2|x1 = 1, x2 = 0)

W (y1, y2|x1 = 0, x2 = 1)

= bc/ad

= (a/b)−1(c/d).

Em ambos os casos, verifica-se novamente que a LR de u2 pode ser expressada em termos de a/b
e c/d, que são as LRs de x1 e x2 Defini-se a função:

q(p, q, u1]) = p1−2u1q. (4.17)

E então a escolha de û2 é feita a partir da relação:

û2 =

{
0, se g(a/b, c/d,û1) > 1

1, caso contrário.

Portanto, o decodificador não necessita todos os valores a, b, c, ed. Tendo as LRs : a/b e c/d é
suficiente.

4.2.2 Decodificador de tamanho N

A decodificação do canal é feita utilizando as saídas yN1 do canal com probabilidade WN(y
N
1 |uN1 ).

Os valores de uNi nessa técnica de decodificação são estimados pelo conjunto de bits congelados Ac e
pela equação (4.15), no qual se obtém:

û1 =


ui, se i ∈ Ac

0, se i ∈ Ac e L
(i)
N (yN1 , û

i−1
1 ) > 1

1, se i ∈ Ac e L
(i)
N (yN1 , û

i−1
1 ) < 1

(4.18)

A equação (4.15) pode ser calculada na forma recursiva, sendo assim:

L
(i)
N (yN1 , u

i−1
1 ) =

{
f(a, b), para i impar
g(a, b, ûi−1), para i par

(4.19)



53

Sendo,

f(a, b) =
a · b+ 1

a+ b
. (4.20)

E,

g(a, b, ûi−1) = a1−2ûi−1 · b, (4.21)

onde

a = L
i/2
N/2(y

N/2
1 ), ûi−11,o ⊕ ûi−11,e e b = L

i/2
N/2(y

N
N/2), û

i−1
1,e . (4.22)

4.2.3 Passos para decodificação SC

Os passos a serem adotados pela codificação serão:

Passo 1: As variáveis que se localizam mais à direita da Figura 26 possuem inicialmente valores
para i = {1, 2, ..., N}, L(1)

1 (yi) = W (yi|ui = 0)W (yi|ui = 1).

Figura 26 – Arquitetura Decodificador SC N = 8.

fonte: Própria autora.

Passo 2: O primeiro bit u1 é necessário para ser decodificado, caso for um bit congelado u1 é
definido como 0, caso contrário atualiza os índices de verossimilhança do lado mais à direita para o mais



54

à esquerda de acordo com (4.20) e (4.21) obtendo LN
1 pretendido. Se LN

1 > 1, u1 é correspondente a 0.
Caso LN

1 < 1 é igual a 1, caso contrario u1 pode ser a 0 ou 1 com probabilidades iguais.
Passo 3: Nesse passo u2 é decodificado, com um processo similar ao Passo 2, porém quando é

calculado LN
2 utiliza-se o valor u1 nas funções de g. Determina-se u2 no momento em que se obtém

LN
2 .

Passo 4: A partir do bit u3 até uN será feita a decodificação de acordo com as informações dos
bits anteriores.

4.2.4 Exemplo decodificação SC para N=8

Para a decodificação de um código com tamanhoN = 8 e taxa de códigoR = 1/3 que é transmitido
por um canal AWGN com Eb/No = 1 dB. Dispõe-se das seguintes informações: A = {4, 6, 8}, sendo
os valores dos bits de informação todos 1, os bits congelados: (u1, u2, u5, u7) correspondem à 1. Os
cálculos das LRs para os bits de informação serão demonstrados na Figura 27. Os cálculos feitos são
baseados em (4.15), designando ui como 0 se LN for maior que 1 e vice-versa. A Figura 27 demonstra
os cálculos feitos para u4.

Figura 27 – Decodificador SC, N = 8.

fonte: Própria autora.

Passo 1: No início as variáveis que estão na extrema direita da Figura 26 são iniciadas como:
{0, 4800;−2, 7848; 0, 8946;−0, 7669; 0, 5275;−2, 3709; 1, 1148;−0, 7829}, sendo esses valores ob-
servações dos canais.

Passo 2: Descobre-se quando u1 é um bit de informação antes de fazer sua decodificação, desde
que os valores congelados são {1, 2, 3, 5} então é possível saber que u1 é um bit congelado e vale 0.

Passo 3: Semelhante ao passo 2, sabe-se que u2 e u3 são bits congelados, portanto eles corres-
pondem à 0, decodificando u4, no momento em que é feita a decodificação a informação de LR é
atualizada da direita para a esquerda, utilizando somente valores numéricos como exemplo. O valor



55

0,1461 é obtido calculando uma função f = 1 + 0, 4800 · (−2, 7848)0, 4800 − 2, 7848 = 0, 1461.
Obtém-se o valor 0, 3592 por uma função g = 0, 14611− 2(u1⊕u2) · 2, 4583 = 0, 3592.

Com valores de u2 e u1 conhecidos antes de fazer a decodificação, os valores restantes são obtidos
de maneira similar, após o cálculo de L8

4 =0,0435, define-se que u4 é 1, pois L8
4 é menor que 1. Os

bits restantes são calculados da mesma maneira na Figura 28 sendo possível observar o resultado geral
da decodificação.

Figura 28 – Decodificador SC N = 8 após todos os passos.

fonte: Própria autora.

4.3 IMPLEMENTAÇÃO COMPUTACIONAL

Nesta seção, apresentamos uma implementação computacional feita por meio de um algoritmo
utilizando o software MATLAB, que foi baseado no algoritmo proposto em (VANGALA, 2018).

O diagrama de blocos a seguir ilustra o funcionamento do Algoritmo proposto.

Figura 29 – Diagrama de Blocos Codificação/Decodificação.

fonte: Própria autora.

O Algoritmo é inicializado propondo-se valores para N,K,Ec e N0, onde Ec corresponde à
energia de símbolo em escala linear da modulação BPSK, No é a densidade espectral de potência do



56

ruído, N é o comprimento do bloco e K o comprimento da mensagem. Com os valores de K e N se
obtém a taxa de bits do canal.

A partir dos dados de entrada, o Algoritmo gera K bits aleatórios em um vetor u de comprimento
N que servirão como mensagem de entrada no codificador, as demais entradas N − K de u serão
fixadas (congeladas) pelo processo de polarização de canal. O Codificador Polar transformará esse
vetor u na palavra-código x da seguinte forma

x = d.F (x, n), (4.23)

onde d é um vetor deN bits incluindo os bits de informação e os bits congelados, e F (x, n) é o n-ésimo
produto de Kronecker da matriz F dada em (4.5). A Equação 4.23 desenvolvida pelo algoritmo, utiliza
(4.1) e (4.12).

Os bits que saem do codificador passam por um Modulador BPSK e por um Canal no qual será
introduzido um ruído AWGN.

Posteriormente, o sinal entrará no Decodificador SC Polar sendo primeiramente demodulado para
então ser decodificado. A decodificação será feita pela técnica de cancelamento sucessivo que foi
apresentada na Seção 4.2, essa decodificação obterá um valor û estimado. Por fim, é feita a comparação
entre os valores u de entrada e û de saída e então será gerado um gráfico com os valores obtidos de
BER em função da razão sinal ruído, Eb/No.

Para obtermos os resultados, foram feitas cinco simulações para os seguintes valores de N e K:

(N,K) = (128, 64; 256, 128; 512, 256; 1024, 512; 2048, 1024)bits,

para gerar um gráfico comparativo entre as curvas obtidas para diferentes valores. Os demais dados
utilizados para inicializar o Algoritmo foram

Ec = 1 ; No = 2

e Eb/No foi variado de 0 a 5 dB.
O gráfico a seguir ilustra as curvas obtidas para valores de N e K variantes.



57

Figura 30 – Gráfico BER por Eb/No.

fonte: Própria autora.

A partir do gráfico da Figura 30 observa-se que ao variar o valor do tamanho N da palavra-código
para diferentes valores de relação sinal-ruído, obtém-se curvas distintas umas das outras. Para valores
de N crescentes, as curvas geradas ficam cada vez mais íngremes e vão se aproximando do Limite de
Shannon, como ilustrado na Figura 30. É possível observar o aumento na eficiência desse código, pois
ao se aproximar do Limite de Shannon, essas curvas possuem uma relação sinal ruído diminuída e
também relação sinal-ruído cada vez menor, para menores valores de Eb/N0 aumenta-se a eficiência
espectral do canal. A partir da polarização do canal utilizada na codificação, de acordo com a teoria
descrita no Capítulo 3, para valores de N tendendo ao infinito os canais polarizados tenderão para
os extremos correspondentes a 0 ou 1, ou seja, para maiores valores de N haverá um aumento na
confiabilidade do canal, dado que os canais ruins utilizados para enviar os bits congelados serão bem
diferentes dos canais bons utilizados para enviar informações.

O limite de Shannon ilustrado na Figura 30 considera uma largura de banda infinita com Eb/No
tendo um valor aproximado por ln(2) = −1, 59.

Em (NIU et al., 2014) foram feitas simulações para diferentes esquemas de codificação, variando
os parâmetros de cada codificação e a relação sinal-ruído para se obter as taxas de erro de blocos (Block

Error Ratio, BLER). É possível observar essas simulações na Figura 31.



58

Figura 31 – Gráfico BLER por Eb/No para diferentes codificações.

fonte: (NIU et al., 2014).

Para obter este resultado, foram utilizados códigos de tamanho N = 1024 para todos os esque-
mas, exceto para o código LDPC que utilizou N = 1056, com taxas de código igual a 1/2, sendo
transmitidos por um canal AWGN com entradas binárias. Para os códigos turbo foram utilizados
dois esquemas de codificação: Acesso Múltiplo por Divisão de Código de Banda Larga (Wide-Band

Code-Division Multiple Access, WCDMA) e LTE, com um máximo de oito iterações. Para os códigos
LDPC utilizou-se o padrão WiMAX e um algoritmo de propagação de crenças (Belief Propagation,
BP) com um número máximo de 200 iterações. Já para os códigos polares foram utilizados tamanhos
de lista para verificação de redundância cíclica na lista de cancelamento sucessivo (Cyclic Redundancy

Check Successive Cancellation List, CA-SCL) de 32 e um valor máximo de lista para verificação
de redundância cíclica auxiliar na lista de cancelamento sucessivo (Cyclic Redundancy Check aided
Successive Cancellation List, aCA-SCL) de 1024, foi utilizado número máximo de 200 iterações no
decodificador BP.

É possível observar nesse gráfico que a codificação polar com decodificação SC apesar de possui
uma menor complexidade, tem uma performance mais fraca em comparação com outras técnicas.
Esse gráfico demonstra que para um mesmo tamanho de palavra código em diferentes técnicas os
códigos polares possuem vantagem em relação aos códigos tubo e LDPC, porém os códigos polares
que possuem essa vantagem são os CA-SCL e aCA-SCL. Nesse trabalho não foi abordado a construção
dos códigos polares descritos no gráfico, porém elas podem ser encontradas em (NIU et al., 2014).



59

5 CONCLUSÃO

Neste trabalho apresentamos um estudo sobre a codificação e a decodificação de códigos polares
utilizando a técnica de polarização de canal. Como vimos, com a polarização de canal é possível
separar canais considerados bons ou ruins através do cálculo de suas capacidades, após a separação
desses canais serão enviados bits de informação nos canais bons para que não sofram degradação e bits
fixados (congelados) nos canais ruins, pois serão enviados os valores desses bits para os decodificadores,
portanto esses bits podem sofrer degradações pelos canais.

Além disso, foi discutido e exemplificado como foram feitas a codificação, que pode ser feita de
duas maneiras: utilizando um circuito de codificação para canais WN e também através de expressões
algébricas utilizando o produto de Kronecker de matrizes, e decodificação, através da técnica de
cancelamento sucessivo de um sinal por meio dos códigos polares, essa técnica consiste em fazer o
caminho reverso da codificação para sucessivamente ir descobrindo os valores de capacidade referentes
aos canais, após finalizada faz a decisão se o valor da saída é 0 ou 1 por meio de uma relação
estabelecida. Foi possível observar que esses códigos possuem uma baixa complexidade de codificação,
tornando-o assim um código de fácil implementação e com uma decodificação com grande eficiência.

Observamos também através da implementação computacional realizada para diferentes compri-
mentos do código, a eficiência dessa codificação e decodificação. Comparando sua relação sinal ruído
com a taxa de erro de bits obtida, vimos que quanto maior o valor de N , mais o sinal se aproxima do
limite da capacidade do canal de Shannon aumentando sua eficiência espectral com menores valores
de taxa de erro de bit. Em uma comparação com diferentes codificações foi demonstrado que códigos
polares são mais eficientes, porém com técnicas de decodificação diferentes do que a utilizada nesse
trabalho.

Diversas pesquisas já foram feitas com o intuito de melhorar cada vez mais as técnicas de codifica-
ção e de decodificação por cancelamento sucessivo. Pesquisas futuras poderão focar em estudar mais
profundamente variações destas técnicas de codificação e decodificação como por exemplo: codificação
na forma sistemática (ARIKAN, 2011), (VANGALA; HONG; VITERBO, 2016) ; uma permutação
na técnica de decodificação SC (PSCD), (VANGALA; VITERBO; HONG, 2014) e puncionamento
(LAMARE, 2017) .



60

REFERÊNCIAS

ARIKAN, E. Channel polarization: A method for constructing capacity-achieving codes for symmetric
binary-input memoryless channels. IEEE Transactions on Information Theory, IEEE, v. 55, n. 7, p.
3051–3073, 2009.

ARIKAN, E. Systematic polar coding. IEEE Communications Letters, IEEE, v. 15, n. 8, p. 860–862,
2011.

COVER, J. A. T. T. M. Elements of Information Theory. [S.l.]: Wiley, 2012.

HAYKIN, S. S. Communication systems. [S.l.]: Wiley, 2001.

HEFEZ, M. L. T. V. A. Códigos Corretores de Erros. [S.l.]: IMPA, 2008.

HUAWEI. Huawei 5G: New Breakthrough on Channel Coding Technology with Polar
Code. 2016. Disponível em: <http://www.huawei.com/en/press-events/news/2016/10/
Huawei-5G-channel-coding-breakthrough>.

HUILGOL, S. Channel Coding Techniques for 5G Using Polar Codes. 2017.

ISCAN, O.; LENTNER, D.; XU, W. A comparison of channel coding schemes for 5g short message
transmission. In: 2016 IEEE Globecom Workshops (GC Wkshps). [S.l.: s.n.], 2016. p. 1–6.

KUMAR, B. A.; RAO, P. T. Overview of advances in communication technologies. In: 2015 13th
International Conference on Electromagnetic Interference and Compatibility (INCEMIC).
[S.l.]: IEEE, 2015. p. 102–106.

LAMARE, R. M. O. e Rodrigo C. de. Codigos polares e puncionamento baseado em polarizacao
para sistemas 5g. XXXV SIMPOSIO BRASILEIRO DE TELECOMUNICACOES E
PROCESSAMENTO DE SINAIS, p. 629 – 633, 2017.

NIU, K. et al. Polar codes: Primary concepts and practical decoding algorithms. IEEE
Communications Magazine, v. 52, n. 7, p. 192–203, 2014.

RYAN, W.; LIN, S. Channel Codes: Classical and Modern. [S.l.]: Cambridge University Press,
2009.

SHAFI, M. et al. 5g: A tutorial overview of standards, trials, challenges, deployment, and practice.
IEEE Journal on Selected Areas in Communications, IEEE, v. 35, n. 6, p. 1201–1221, 2017.

SHANNON, C. E. A mathematical theory of communication. The Bell System Technical Journal,
Nokia Bell Labs, v. 27, n. 3, p. 379–423, 1948.

SHARMA, A.; SALIM, M. Polar code: The channel code contender for 5g scenarios. 2017
International Conference on Computer, Communications and Electronics (Comptelix), IEEE, p.
676–682, 2017.

VANGALA, H. Polar Codes. 2018. Disponível em: <http://www.polarcodes.com/>.

VANGALA, H.; HONG, Y.; VITERBO, E. Efficient algorithms for systematic polar encoding. IEEE
Communications Letters, IEEE, v. 20, n. 1, p. 17–20, 2016.

http://www.huawei.com/en/press-events/news/2016/10/Huawei-5G-channel-coding-breakthrough
http://www.huawei.com/en/press-events/news/2016/10/Huawei-5G-channel-coding-breakthrough
http://www.polarcodes.com/


61

VANGALA, H.; VITERBO, E.; HONG, Y. Permuted successive cancellation decoder for polar codes.
In: 2014 International Symposium on Information Theory and its Applications. [S.l.]: IEEE,
2014. p. 438–442.

WANG, R.; LIU, R. A novel puncturing scheme for polar codes. IEEE Communications Letters,
IEEE, p. 2081–2084, 2014.

WASSERMAN, D. Technical Report 2054: Polar Codes. [S.l.]: Spawar Systems Center Pacific,
San Diego, CA, USA, 2014.


	Folha de rosto
	Dedicatória
	Agradecimentos
	Epígrafe
	Resumo
	Abstract
	Lista de abreviaturas e siglas
	Introdução
	Revisão de Conceitos
	Teoria da Informação
	Capacidade do canal

	Códigos de bloco lineares

	Polarização de Canal
	Conceitos Preliminares
	Combinação de Canal
	Divisão de Canal
	Exemplo de Polarização de Canal para BEC

	Codigos Polares
	Codificação dos Códigos Polares
	Expressões Algébricas
	Exemplo Codificação

	Decodificação dos Códigos Polares por SC
	Decodificador de tamanho 2
	Decodificador de tamanho N
	Passos para decodificação SC
	Exemplo decodificação SC para N=8

	Implementação Computacional

	Conclusão
	Referências