UNIVERSIDADE ESTADUAL PAULISTA "JÚLIO DE MESQUITA FILHO" CAMPUS DE SÃO JOÃO DA BOA VISTA LEONARDO TERÇAS Codificação de Canal para Comunicações Ultra Confiáveis em Sistemas 5G São João da Boa Vista 2019 LEONARDO TERÇAS Codificação de Canal para Comunicações Ultra Confiáveis em Sistemas 5G Trabalho de Graduação apresentado ao Conselho de Curso de Graduação em Engenharia Eletrônica e de Telecomunicações do Campus de São João da Boa Vista, Universidade Estatual Paulista "Júlio de Mesquita Filho", como parte dos requisitos para obtenção do diploma de Graduação em Engenharia Eletrônica e de Telecomunicações . Orientador: Profa. Dra. Cintya Wink de Oliveira Benedito São João da Boa Vista 2019 Terças, Leonardo Codificação de canal para comunicações ultra confiáveis em sistemas 5G / Leonardo Terças -- São João da Boa Vista, 2019. 79 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”. Orientadora: Profa. Dra. Cintya Wink de Oliveira Benedito Bibliografia 1. Codificação 2. Códigos corretores de erros (Teoria da informação) 3. Sistemas de comunicação sem fio 4. Teoria da informação 5. Telecomunicações 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 ELETRÔNICA E DE TELECOMUNICAÇÕES TRABALHO DE CONCLUSÃO DE CURSO CODIFICAÇÃO DE CANAL PARA COMUNICAÇÕES ULTRA CONFIÁVEIS EM SISTEMAS 5G Aluno: Leonardo Terças Orientador: Prof.ª Dr.ª Cintya Wink de Oliveira Benedito Banca Examinadora: - Cintya Wink de Oliveira Benedito (Orientadora) - Edgar Eduardo Benitez Olivo (Examinador) - Ivan Aritz Aldaya Garde (Examinador) A ata da defesa com as respectivas assinaturas dos membros encontra-se no prontuário do aluno (Expediente nº 22/2019) São João da Boa Vista, 05 de dezembro de 2019 Dedico este trabalho ao meu pai Paulo Rogério Terças, à minha mãe Sandra Regina Mirabelli Terças e ao meu irmão Rafael Terças, por todo incentivo, esforço e confiança depositados. AGRADECIMENTOS À minha família por toda confiança, carinho e esforço, que mesmo longe se mostraram presentes, me incentivando e dando forças em todos os momentos desta fase da minha vida. À minha orientadora, Profa. Dra. Cintya Wink de Oliveira Benedito, por toda disposição, atenção, paciência e orientação durante o desenvolvimento deste trabalho. Ao meu co-orientador de iniciação científica, Profo. Dr. Carlos Héracles Morais de Lima, por despertar em mim o interesse pelo estudo, pesquisa e ramo acadêmico. Aos membros da banca examinadora pela disponibilidade e atenção dedicada ao trabalho, assim como, por suas sugestões. À UNESP SJBV e todos os professores e funcionários que compartilharam comigo suas experiên- cias. À FAPESP pelo financiamento da pesquisa que auxiliou no desenvolvimente deste trabalho. Aos meus amigos da turma 015, por todo o apoio e amizade durante os 5 anos de graduação, principalmente aos meus amigos de grupo Carolina Ronchini, Carlos Zan e Juliana Menzinger pela paciência, companheirismo e noites mal dormidas. Aos meus veteranos que sempre me incentivaram e não me fizeram desistir da caminhada, mos- trando a garra e o caminho para vencer, principalmente à Letícia Fidanza e Melissa Santos pelos sábios conselhos. Aos meus amigos com quem dividi moradia na graduação, por toda alegria transpassada e histórias inesquecíveis vividas, muito obrigado Thiago Ogawa, Sidney Borges e Bruno Fernandes. Aos amigos conquistados na UNESP, por trazerem grandes reflexões e tornar a caminhada da graduação menos cansativa, principalmente a Allan Branco, Laura Almeida, Lanna Jeacomini e Marcelo Pereira por sempre estarem ao meu lado. Aos meus colegas de trabalho na Atlética, que tornaram-se amigos para a vida, muito obrigado pelas experiências compartilhadas e discussões construtivas, principalmente à Felipe Stringa, Guilherme Nascimento, Lucas Viotto e Renato Ferreira por sempre estarem comigo quando precisei. E por fim à Deus pelo seu carinho e grande amor, que me dá força para seguir em frente em meio as dificuldades encontradas. Eu só tenho a agradecer! "Sucesso significa realizar seus próprios sonhos, cantar sua própria canção, dançar sua própria dança, criar do seu coração e apreciar a jornada, confiando que não importa o que aconteceça, tudo ficará bem. Criar sua própria aventura!" (Elana Lindquist) RESUMO Codificação de canal nada mais é que uma técnica onde bits de redundância são inseridos na mensagem de interesse, de modo que, durante a recepção da mesma, estes possam ser utilizados para detectar e corrigir erros. Esta técnica apresentada por Shannon em 1948, vem sendo alvo de diversas pesquisas, que buscam desenvolver e aprimorar bons códigos corretores de erros, para atingir a capacidade de canal prevista pelo matemático. Visando sistemas de comunicação sem fio de quinta geração (5G), algumas técnicas de codificação de canal se tornaram candidatas para serem utilizadas em suas transmissões. O objetivo deste trabalho, é realizar o estudo e a comparação de duas destas técnicas, os códigos convolucionais e os códigos polares, visando a aplicação em comunicações ultraconfiáveis e de pacotes curtos em sistemas 5G. Assim, foi realizado o estudo dos codificadores e decodificadores destes códigos e uma implementação computacional para avaliar o desempenho dos mesmos. Os resultados mostram que os códigos polares possuem um bom desempenho em correção e detecção de erro, entretanto possuem alta latência, utilizando o decodificador por cancelamento sucessivo. Já os códigos convolucionais se sobressaem em latência, entretanto não atingem as métricas esperadas em correção e detecção de erro. PALAVRAS-CHAVE: Codificação de Canal. Códigos Convolucionais. Códigos Polares. 5G. ABSTRACT Channel coding is nothing more than a technique where redundancy bits are inserted into the message of interest, so that while reception they can be used to detect and correct errors. This technique introduced by Shannon in 1948, has been the subject of several researches that seek to develop and improve good error-correcting codes to achieve the channel capacity predicted by the mathematician. Aiming at fifth generation wireless communication systems (5G), some channel coding techniques have become candidates for use in their transmissions. The objective of this work is to study and compare two codes, convolutional and polar codes, aiming at application in ultra-reliable and short packet communications in 5G systems. Thus, the study of the coders and decoders of these codes and a computational implementation to evaluate their performance was performed. The results show that polar codes perform better in error correction and detection, however they have high latency using the successive cancellation decoder. Convolutional codes, however, perform better in latency, but do not meet expected metrics in error correction and detection. KEYWORDS: Channel Coding. Convolutional Codes. Polar Codes. 5G. LISTA DE ILUSTRAÇÕES Figura 1 Canal binário sem ruído. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Figura 2 Canal binário simétrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Figura 3 Capacidade canal binário simétrico. . . . . . . . . . . . . . . . . . . . . . . . 20 Figura 4 Canal binário com apagamento. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Figura 5 Canal gaussiano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Figura 6 Código de bloco. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Figura 7 Máquina de estados (1,1,2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Figura 8 Esquema simplificado da codificação convolucional. . . . . . . . . . . . . . . . 28 Figura 9 Máquina de estados código convolucional (2,1,7). . . . . . . . . . . . . . . . . 29 Figura 10 Representação diagrama de estados. . . . . . . . . . . . . . . . . . . . . . . . 33 Figura 11 Máquina de estados código convolucional (2,1,3). . . . . . . . . . . . . . . . . 33 Figura 12 Diagrama de estados código convolucional (2,1,3). . . . . . . . . . . . . . . . 34 Figura 13 Codificação da mensagem u = (10111). . . . . . . . . . . . . . . . . . . . . . 34 Figura 14 Diagrama de treliça código convolucional (2,1,3). . . . . . . . . . . . . . . . . 35 Figura 15 Codificação da mensagem u = (10111). . . . . . . . . . . . . . . . . . . . . . . 35 Figura 16 Diagrama de treliça código convolucional (2,1,2). . . . . . . . . . . . . . . . . 38 Figura 17 Decodificação utilizando o algoritmo de Viterbi. . . . . . . . . . . . . . . . . . 38 Figura 18 Caminho escolhido pela decodificação utilizando o algoritmo de Viterbi. . . . . 38 Figura 19 Canal sem memória. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Figura 20 Canal para N = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Figura 21 Canal para N = 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Figura 22 Canal para N = 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Figura 23 Canal geral WN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Figura 24 I(W1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Figura 25 I(W2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Figura 26 I(W4). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Figura 27 I(W8). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Figura 28 Canais polarizados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Figura 29 Exemplo circuito da transformação F⊗3. . . . . . . . . . . . . . . . . . . . . . 54 Figura 30 Codificação u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Figura 31 Exemplo arquitetura de decodificação SC com N = 8. . . . . . . . . . . . . . . 57 Figura 32 Exemplo decodificação SC com N = 8. . . . . . . . . . . . . . . . . . . . . . . 59 Figura 33 Ciclo de clock do processador nos decodificador SC. . . . . . . . . . . . . . . 62 Figura 34 Arquiterura em árvore SC com N = 8 e R = 1/2. . . . . . . . . . . . . . . . . . 62 Figura 35 Exemplo arquitetura de decodificação SSC com N = 8. . . . . . . . . . . . . . 63 Figura 36 Exemplo decodificação SSC com N = 8. . . . . . . . . . . . . . . . . . . . . . 64 Figura 37 Ciclo de clock do processador no decodificador SSC. . . . . . . . . . . . . . . 67 Figura 38 Decodificadores em árvore SSC para diferentes taxas. . . . . . . . . . . . . . . 67 Figura 39 Simulação da BER para códigos convolucionais com (N,k) = (64,32; 128,64; 256,128; 512,256; 1024,512; 2048,1024) . . . . . . . . . . . . . . . . . . . . . 70 Figura 40 Simulação da BER para códigos polares com (N,k) = (64,32; 128,64; 256,128; 512,256; 1024,512; 2048,1024) . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Figura 41 BER com taxa 1/2 para (N,k) = (64,32; 128,64; 256,128; 512,256) . . . . . . . 72 Figura 42 Latência de processamento com taxa 1/2 . . . . . . . . . . . . . . . . . . . . . 73 Figura 43 Throughput com taxa 1/2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Figura 44 Clocks necessários para decodificar diferentes comprimentos de palavras . . . . 74 Figura 45 Bits decodificados por clock para diferentes comprimento de palavra . . . . . . 75 LISTA DE ABREVIATURAS E SIGLAS 5G Quinta geração das comunicações móveis AWGN Additive White Gaussian Noise BEC Binary Erasure Channel BER Bit Error Rate BPSK Binary Phase Shift Keying BSC Binary Symmetric Channel IoT Internet of Things LDPC Low Density Parity Check LR Likelihood Ratio MTC Machine Type Communication SC Successive Cancellation Decoder SSC Simplified Successive Cancellation Decoder URC Ultra Reliability Communications V.A. Variável Aleatória LISTA DE SÍMBOLOS µAC Bits congelados µA Bits de informação B Banda do canal c Palavra-código ĉ Estimativa de uma palavra código gerada pelo decodificador C Código BC Base de um subespaço C Capacidade do canal d Distância mínima de Hamming D Variável de atraso unitário dh Distância de Hamming e Bit apagamento Eb Energia do bit F⊗n Produto de Kronecker Fq Subespaço de q elementos gi Sequência geradora g(D) Polinômio gerador de um codificador G Matriz geradora H Matriz controle de paridade H(X) Entropia I(X;Y ) Informação mútua k Comprimento do código de saída L (i) N (yN 1 ,u i−1 1 ) Razão de verossimilhança m Mensagem de interesse m̂ Estimativa da mensagem recebida pelo receptor M Quantidade de memórias do codificador n Comprimento do código de entrada N Quantidade de canais N ′ Quantidade de simulações realizadas N0 Densidade de potência do ruído N ′A Número de ocorrências de um evento A ℵ Variância N0 Nós bits congelados N1 Nós bits de informação NR Nós combinação de bits congelados e de informação P Matriz de ordem k × (n− k) P Potência de transmissão p Probabilidade de erro p(x, y) Probabilidade conjunta p(xk) Probabilidade de um evento de interessse P ′t Matriz P ′ transposta q Quantidade de elementos r Mensagem recebida R Taxa de codificação Rn Matriz permutação de canais T Throughput û Vetor de bits estimados u(D) Polinômio de entrada de um codificador u Vetor de entrada em um codificador v(D) Polinômio de saída de um codificador v Vetor de saída em um codificador W Canal sem memória wH(u) Peso de Hamming x Evento de interesse X Variável aleatória discreta Xi Entrada canal de tempo discreto Y Variável aleatória Yi Saída canal de tempo discreto Zi Ruído canal de tempo discreto SUMÁRIO 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 REVISÃO DE CONCEITOS . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Teoria da Informação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Codificação de Canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.1 Código de Blocos Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 CÓDIGOS CONVOLUCIONAIS . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2.1 Algoritmo de Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 CÓDIGOS POLARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1 Polarização de Canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3 Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3.1 Decodificador por Cancelamento Sucessivo . . . . . . . . . . . . . . . . . . . 57 4.3.2 Decodificador por Cancelamento Sucessivo Simplificado . . . . . . . . . . . . 63 5 IMPLEMENTAÇÃO, ANÁLISES E RESULTADOS . . . . . . . . . . . . . . 69 6 CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 15 1 INTRODUÇÃO O sistema de quinta geração de comunicações sem fio 5G não será apenas uma evolução das redes atuais, será uma tecnologia que irá revolucionar a maneira como vivemos, interagimos e fazemos negócios. O sistema 5G promoverá meios técnicos para, “ter a sociedade totalmente conectada” e demandará uma nova estrutura de planejamento, implantação, operação e otimização para interagir plenamente com as novas tecnologias digitais emergentes no mercado. A implementação do sistema 5G está prevista para ocorrer a partir de 2020 e tornou-se grande alvo de diversas pesquisas, que buscam desenvolver e aprimorar técnicas e tecnologias para que a proposta deste sistema seja alcançada. Este sistema irá disponibilizar novos recursos e possibilidades, como os serviços de alta capacidade, a implantação massiva de objetos inteligentes (Internet of Things - IoT) e serviços com alta confiabilidade e/ou baixa latência, [TAHIR, SCHWARZ e RUPP 2017, OLIVEIRA e LAMARE 2017]. As aplicações comerciais atuais visam principalmente as comunicações orientadas a humanos, que focam em assegurar uma boa conectividade na maior parte do tempo, entretanto em situações onde o sinal é degradado a taxa de transmissão é nula. Já os sistemas emergentes, cuja transmissões são orientadas a máquinas dependem criticamente da disponibilidade ininterrupta dos enlaces de rádio, mesmo que a qualidade da conexão fique baixa, [5GPPP 2015]. Shannon, em 1948, mostrou que uma comunicação livre de erros em um canal com ruído é possível, desde que uma estratégia de codificação de canal apropriada seja utilizada e a taxa de transmissão de informação seja menor ou igual a capacidade do canal, [SHANNON 1948]. Deste modo, diversas pesquisas vêm sendo desenvolvidas sobre esquemas de codificação de canal, com o objetivo de atingir a capacidade do canal prevista pela teoria de Shannon. A codificação de canal é uma técnica onde bits de redundância são inseridos de maneira estruturada no transmissor (codificação), de modo que no receptor durante a decodificação, esta redundância auxilie a detectar e corrigir possíveis erros adquiridos durante a transmissão. Assim, códigos com alto desempenho de codificação e decodificação são essenciais para os futuros sistemas de comunicação sem fio. Alguns códigos foram selecionados como candidatos para a comunicação sem fio de quinta geração, como os códigos convolucionais, os códigos turbo, os códigos LDPC (em inglês, Low-density-parity-check) e os códigos polares [TAHIR, SCHWARZ e RUPP 2017]. Neste trabalho iremos comparar o desempenho de técnicas de codificação de canal em cenários baseados na comunicação entre máquinas (MTC, em inglês Machine Type Communication), onde a quantidade de dados de informação é comparável aos dados de controle, ou seja, os sistemas MTC são compostos por pacotes curtos. Estes cenários estarão operando no modo previsto para as comunicações ultra confiáveis (URC, em inglês Ultra-Reliable Communication), que é um modo de operação ainda não existente nos sistemas atuais, que prevê a sustentação de uma qualidade de serviço mínima durante quase 100% do período de conexão [METIS 2012 - 2015, METIS 2015 - 2017, POPOVSKI 2015]. Serão avaliadas duas técnicas de codificação de canal, os códigos convolucionais e os códigos polares, pois tais códigos apresentam grandes chances de compor a nova geração, devido a baixa complexibilidade de implementação e o alto desempenho [ISCAN, LENTNER e XU 2016, SYBIS 16 et al. 2016]. As simulações serão realizadas através de implementação computacional no software MATLAB, onde palavras de comprimento k serão codificadas, transmitidas por um canal AWGN (Additive White Gaussian Noise) e decodificadas por um receptor, a fim de avaliar a taxa de erro de bit (BER - Bit Error Rate), a latência de processamento, que é o tempo utilizado para codificar e decodificar uma mensagem de interesse, e a taxa de transferência de informação (Throughput), que é a quantidade de bits que são decodificados por segundo levando em consideração um ciclo de clock do processador [SARKIS e GROSS 2013b, LEROUX et al. 2011]. O presente trabalho está organizado da seguinte maneira: no Capítulo 2, será realizada uma breve revisão sobre a teoria da informação e codificação de canal. No Capítulo 3, abordaremos os códigos convolucionais, exemplificando como é realizada sua codificação e decodificação. No Capítulo 4, descreveremos os códigos polares, abordando a técnica de polarização de canal que o código faz uso, sua codificação e dois tipos de decodificação que podem ser utilizados por este código. No Capítulo 5, serão abordadas as métricas que serão analisadas nas simulações, as implementações computacionais realizadas e os resultados obtidos. Por fim, no Capítulo 6, serão apresentadas as conclusões obtidas pelo presente trabalho. 17 2 REVISÃO DE CONCEITOS Neste capítulo iremos realizar uma breve revisão de conceitos importantes que serão necessários para o desenvolvimento do trabalho. Na Seção 2.1 serão apresentados os conceitos de entropia e informação mútua, para enfim definir a capacidade de um canal. E na Seção 2.2 será abordada a codificação de canal, juntamente com o estudo dos códigos de bloco lineares, apresentando conceitos básicos destes códigos e exemplos de aplicação. As definições apresentadas neste capítulo podem ser encontradas em [COVER e THOMAS 2006, RYAN e LIN 2009, HAYKIN 2001, RAPPAPORT 2008]. 2.1 TEORIA DA INFORMAÇÃO A teoria da informação proposta por Shannon [SHANNON 1948], desenvolve estudos de conceitos relacionados a quantificação, armazenamento e transmissão de informação, os quais são de extrema importância para o ramo das comunicações. Uma das medidas mais importantes da teoria da informação é a entropia, este parâmetro pode ser definido como a quantidade média de informação de um evento de interesse, associado a uma variável aleatória. Já informação pode ser definida como a quantidade de incerteza de um processo em termos probabilísticos, onde incerteza, é uma “surpresa” na ocorrência de um evento. Partindo de um evento de interesse, x = xk com probabilidade p(xk), a quantidade de informação pode ser relacionada com o inverso da probabilidade de ocorrência. Definição 2.1.1 Define-se a quantidade de informação de um evento de uma variável aleatória discreta x = xk com probabilidade p(xk), como I[xk] = log2 [ 1 p(xk) ] = − log2 p(xk). (2.1) Deste modo, a média da quantidade de informação, definida como a medida de informação média por símbolo, pode ser dada da seguinte forma E[I(xk)] = − k∑ i=1 p(xi) log2[p(xi)]. (2.2) Assim, definimos entropia da seguinte forma. Definição 2.1.2 Assumindo X uma fonte discreta e sem memória, com função massa de probabilidade p(x) = P [X = x], com x = (x0 . . . xn). A entropia de X é definida da seguinte forma H(X) = − ∑ p(x) log2[p(x)]. (2.3) Exemplo 2.1.1 Considere uma função massa de probabilidade p(x) assumindo os seguintes valores 18 X =  1 2 , x = a; 1 4 , x = b; 1 4 , x = c. Utilizando (2.3), temos que o valor de entropia será H(X) = −1 2 log2( 1 2 )− (1 4 ) log2( 1 4 )− 1 4 log2( 1 4 ) = 3 2 bits. Outra medida importante da teoria da informação é a informação mútua, que é a quantidade de informação que uma variável aleatória contém em relação a outra variável aleatória, ou seja, é a redução de incerteza de uma variável aleatória por estar relacionada com outra. Definição 2.1.3 Sejam X e Y duas variáveis aleatórias com função densidade de probabilidade conjunta dada por p(x, y) e, com funções densidade de probabilidade marginais p(x) e p(y). A informação mútua associada a este par de variáveis aleatórias é dada por I(X;Y ) = ∑ x,y p(x, y) log2 [ p(x, y) p(x)p(y) ] . (2.4) Pode-se simplificar a Equação 2.4 de modo que I(X;Y ) = H(X)−H(X|Y ) = H(Y )−H(Y |X). (2.5) Esta medida é importante para transmissões de dados pois com ela é possível mensurar a eficiência de um canal. Se as informações enviadas são dependentes, a informação mútua será maior, estabele- cendo assim uma comunicação confiável. Caso estas variáveis sejam independentes, haverá redução de incerteza e a informação mútua será nula, caracterizando uma comunicação não confiável. Em situações onde variáveis aleatórias são contínuas, a entropia diferencial não será uma soma e sim uma integral de valores. Definição 2.1.4 Seja X uma variável aleatória contínua, com função densidade de probabilidade p(x). A entropia é obtida por H(X) = − ∫ x p(x) log2[p(x)]dx. (2.6) De modo análogo, temos a definição de informação mútua para o caso contínuo. Definição 2.1.5 Sejam X e Y variáveis aleatórias contínuas, com função massa de probabilidade conjunta p(x, y) e funções massa de probabilidade marginais p(x) e p(y), temos a seguinte equação I(X;Y ) = ∫∫ x,y p(x, y) · log2 [ p(x, y) p(x)p(y) ] dxdy. (2.7) Com o conceito de informação mútua podemos definir a capacidade de um canal, que tanto no caso discreto como no caso contínuo, nada mais é do que o limite da taxa em que uma informação pode ser transmitida de forma confiável através de um canal de comunicação. 19 Definição 2.1.6 Define-se capacidade de canal como sendo a taxa máxima de informação que este canal suporta, levando em consideração todas as possíveis distribuições das prováveis entradas, ou seja, a capacidade C de um canal é C = max p(x) I(X;Y ). (2.8) Vale salientar, que a capacidade do canal é medida em bits por uso do canal. A seguir, veremos alguns exemplos de canais importantes e o cálculo de suas respectivas capacidades. Exemplo 2.1.2 Na Figura 1 podemos observar um canal binário sem ruído, ou seja, um canal ideal. Figura 1 – Canal binário sem ruído. X 0 1 0 1 Y Fonte: Próprio autor. Neste canal, a mensagem que é transmitida é recebida, ou seja, P [Y = 1|X = 1] = P [Y = 0|X = 0] = 1 e P [Y = 0|X = 1] = P [Y = 1|X = 0] = 0. Para casos onde P [X = 1] e P [X = 0] aproximam-se de 0.5, a capacidade do canal será 1 bit por uso do canal, que é a informação máxima que pode ser enviada. Exemplo 2.1.3 Na Figura 2 temos o chamado Canal Binário Simétrico (Binary Symmetric Channel - BSC). Neste canal a probabilidade de se transmitir um bit 0 e receber um bit 1 é a mesma que se transmitir um bit 1 e receber um bit 0, ou seja, P [Y = 0|X = 1] = P [Y = 1|X = 0] = p. Figura 2 – Canal binário simétrico. X 0 1 0 1 Y p p 1 - p 1 - p Fonte: Próprio autor. Sabendo que P [Y = 1|X = 1] = P [Y = 0|X = 0] = 1−p, a capacidade do canal seráC = 1−H(p), onde H(p) = −p log2(p)− (1− p) log2(1− p), que é a entropia de uma V.A. binária, por exemplo, se 20 a probabilidade do canal for p = 0.5 então a capacidade do canal será nula, pois haverá incerteza do bit transmitido e qual será recebido, ou seja, toda a informação do canal será perdida. Entretanto, conforme p −→ 0 ou p −→ 1, melhor será o desempenho do canal aproximando-se de um canal ideal, como pode ser observado na Figura 3. Figura 3 – Capacidade canal binário simétrico. Probabilidade de Erro - p 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 C a p a c id a d e d o C a n a l - C 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Canal BSC Fonte: Próprio autor. Exemplo 2.1.4 Na Figura 4 temos o Canal Binário com Apagamento (Binary Erasure Channel - BEC). Neste canal têm-se duas possíveis entradas, entretanto, na saída há uma terceira possibilidade, conhecida como apagamento, que representa um bit que foi corrompido na propagação pelo canal. Esta terceira saída é representada por e e a probabilidade de ocorrência é dada por P [Y = e|X = 1] = P [Y = e|X = 0] = p. Figura 4 – Canal binário com apagamento. X 0 1 0 1 Y p p 1 - p 1 - p e Fonte: Próprio autor. A capacidade desse canal é C = 1− p. Neste canal, ao receber um bit 0 ou 1, tem-se a certeza que os mesmos foram enviados e, caso seja recebido o apagamento, o mesmo pode ser reenviado. 21 Exemplo 2.1.5 Na Figura 5 temos o Canal Gaussiano que é um canal de tempo discreto representado por Yi = Xi + Zi, (2.9) onde, a saída do canal Yi é dada pela soma da entrada Xi com um ruído aditivo gaussiano e branco (Additive White Gaussian Noise - AWGN) Zi de média 0 e variância ℵ, no tempo i. O ruído Zi é independente da entrada Xi. Figura 5 – Canal gaussiano. X + i Z i Y i Fonte: Próprio autor. Para o cálculo da capacidade, temos alguns casos a considerar: • Se a variância do ruído é igual a zero, então a informação de saída será igual a informação da entrada, deste modo, o canal pode transmitir um número real arbitrário sem erros com a capacidade deste canal sendo infinita. • Se a variância do ruído é maior que zero sem restrições de entrada, então a saída pode distinguir os dados recebidos com uma pequena probabilidade de erro, este cenário também possui capacidade infinita. • Se a entrada possui alguma restrição então a capacidade do canal não será infinita. Uma limitação comum em uma transmissão é a potência (P ). Podemos assumir que E[X2] 6 P e σ2 = ℵ, (2.10) onde σ2 é a variância. E, considerando que o ruído é independente da entrada do canal, temos E[Y 2] = E[X2] + E[Z2] 6 P + ℵ. (2.11) Assim, através da Equação 2.8 e da Equação 2.11, a capacidade de informação de um canal gaussiano com restrição de potência P , será dada da seguinte forma C = max p(x)]6P 1 2 log2 ( 1 + P ℵ ) , (2.12) 22 onde C é dada em bits por transmissão. Além disso, se o canal for limitado em banda B, a capacidade do canal será da seguinte forma C = B log2 ( 1 + P ℵ ) , (2.13) onde C é dada em bits/s, a banda B do canal em Hz e P/ℵ é a razão sinal-ruído, dada em dB. 2.2 CODIFICAÇÃO DE CANAL A codificação de canal é frequentemente usada em sistemas de comunicação digital para tentar proteger a informação do ruído e da interferência e, desse modo, reduzir o número de erros de bits. Esta codificação consiste na inserção de bits de redundância no sinal de informação, e estes bits adicionais visam ajudar na detecção e correção de erros proporcionando uma maior confiabilidade na informação recebida. A codificação do canal é, então, o processo em que uma redundância controlada é adicionada à informação objetivando a detecção e a correção de erros introduzidos pelas características do canal. Existem dois tipos principais de códigos corretores de erros: os códigos de bloco e os códigos convolucionais. Os códigos convolucionais serão apresentados no Capítulo 3. Na Subseção 2.2.1 serão apresentados os códigos de bloco, para que no Capítulo 4 os códigos polares, que formam uma classe especial dos códigos de bloco, sejam melhor desenvolvidos. 2.2.1 Código de Blocos Lineares Um código de bloco linear é caracterizado pelos parâmetros (n, k), onde n é o comprimento do código e k é sua dimensão. Ele é denominado código de bloco pois durante a codificação, uma sequência de k bits terá adicionada n− k bits de redundância gerando assim, uma nova palavra de n bits, sendo n > k, como ilustrado na Figura 6. Figura 6 – Código de bloco. Bits de Informação Redundância k n - k Fonte: Próprio autor. Definição 2.2.1 Seja Fq um corpo finito de 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 de dimensão k de F n q . Para valores de q = 2 o código é denominado binário e de q = 3 esse código é denominado ternário. Para q = n, dizemos que o código é q-ário. Além disso, a quantidade de palavras-código de um código C(n, k) sobre Fq é qk e a taxa do código é dada pela razão R = k/n. Exemplo 2.2.1 A partir de F 4 2 considere um código C de parâmetros (n, k) iguais a (4, 2). Este código possui 16 palavras-código pois qk = 24 = 16, e taxa de codificação R = 2 4 = 1 2 . As palavras-código 23 deste código de bloco linear são apresentadas a seguir C = (0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111). Definição 2.2.2 Sejam dois vetores, u = (u1, . . . , un) e v = (v1, . . . , vn) ∈ F n q , a distância de Hamming dh(u, v) destes vetores, será a quantidade de coordenadas que estes vetores diferem entre si. Exemplo 2.2.2 Considerando os vetores u = (0010), v = (0111) e w = (1010) em F 4 2 , a distância de Hamming entre eles será: dh(0010, 0111) = 2, dh(0010, 1010) = 1, dh(1010, 0111) = 3. Propriedade 2.2.1 Sejam u e v dois vetores ∈ F n q , as seguintes propriedades são válidas: 1. dh(u, v) ≥ 0; 2. dh(u, v) = dh(v,u); 3. dh(u, v) ≤ dh(u,w) + dh(w, v). Definição 2.2.3 Seja C um código de bloco linear. A distância mínima de Hamming deste código é definida por d(C) = min[dh(u, v)], (2.14) para todo u, v ∈ C e u 6= v. Exemplo 2.2.3 Considere o código C = {0000, 1110, 1001, 1011} ⊂ F 4 2 . Calculando-se a distância de Hamming, temos que dh(0000, 1110) = 3; dh(1110, 1001) = 3; dh(0000, 1001) = 2; dh(1110, 1011) = 2; dh(0000, 1011) = 3; dh(1001, 1011) = 1. Deste modo, a distância mínima de Hamming deste código é d(C) = 1. Definição 2.2.4 Define-se peso de Hammming wh(u) de um vetor u, como sendo o número de compo- nentes não nulos contidos no vetor. Deste modo, o peso mínimo de Hamming w(C) de um código C é aquele que possui o menor peso das palavras-código. Exemplo 2.2.4 Considerando o código do exemplo anterior, o peso das palavras-código de C são: wh(1110) = 3, wh(1001) = 2, wh(1011) = 3. Portanto, o peso mínimo de C é igual a w(C) = 2. 24 Teorema 2.2.1 Seja C um código e u e v dois vetores pertencentes à C. Tem-se que: 1. dh(u, v) = wh(u− v). 2. d(C) = w(C). Neste trabalho será utilizada somente a distância mínima de Hamming, assim, para facilitar a notação, iremos omitir o índice h. Em casos com número binários, a Condição 1 do Teorema 2.2.1 equivale a operação mod-2 entre os vetores, para avaliar o peso do vetor resultante, d(u, v) = w(u ⊕ v). Exemplo 2.2.5 Considere dois vetores u = (10101) e v = (11101). A distância de Hamming será d(u, v) = w(u ⊕ v) = w(10101 ⊕ 11101) = w(01000). Deste modo, temos que d(u, v) = 1. Definição 2.2.5 Um código de bloco C com parâmentros (n, k) e distância mínima de Hamming d, é representado com parâmetros (n, k, d). Teorema 2.2.2 Seja um código de bloco C com parâmentros (n, k, d), se 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. Definição 2.2.6 Seja Fq um corpo finito e C ⊂ F n q o código de bloco linear com parâmetros (n, k, d) e qk palavras-código. Se BC = {G0, G1, . . . , Gk−1} é uma base de C, então a matriz cujas linhas são os vetores Gi = (gi,0, . . . , gi,n−1), com i = 1, . . . , k, ou seja, G =  G0 G1 ... Gk−1  =  g0,0 g0,1 . . . g0,n−1 g1,0 g1,1 . . . g0,n−1 ... ... . . . ... gk−1,0 gk−1,1 . . . gk−1,n−1.  , é chamada de matriz geradora do código C. Vale salientar que existe mais de uma base de C, ou seja, a matriz geradora não é única. Deste modo, independente da escolha da base tem-se uma matriz G. Exemplo 2.2.6 Considere o código C = {0000, 1110, 1000, 1011}. Uma das possibilidades da matriz geradora para C é dada por G =  1 1 1 0 1 0 0 0 1 0 1 1  . 25 Seja C um código com parâmetros (n, k, d) e matriz geradoraG, e seja u = (u0, u1, . . . , uk−1) ∈ F k q a mensagem a ser codificada. As palavras-código de C podem ser dadas pela combinação linear das linhas G0, G1, . . . , Gk−1 de G, com os k bits de u, ou seja v = u ·G (2.15) = u0 ·G0 + u1 ·G1 + · · ·+ uk−1 ·Gk−1. (2.16) Exemplo 2.2.7 Considere C um código com parâmetros (5, 3) em F 5 2 . Inicialmente para construirmos G, é necessário que uma base para C seja definida. Baseado em k e n, sabe-se que a base BC deverá possuir 3 vetores com 5 bits. Dentre as 25 palavras possíveis, escolhemos 3 vetores que sejam linearmente independentes, portanto, BC = {10111, 01011, 00101}, é uma base para C. Assim, G será dada da seguinte forma G =  1 0 1 1 1 0 1 0 1 1 0 0 1 0 1  . (2.17) As possíveis entradas considerando F 3 2 , são {000, 100, 010, 001, 110, 011, 101, 111}. Dessa forma, a codificação será dada por (2.15). (000) ·G = (00000); (100) ·G = (10111); (001) ·G = (00101); (101) ·G = (10010); (010) ·G = (01011); (110) ·G = (11100); (011) ·G = (01110); (111) ·G = (11001). Logo, C = {00000, 00101, 01011, 01110, 10111, 10010, 11100, 11001}. Para identificar uma mensagem enviada u a partir de uma mensagem recebida v é necessário mostrar que existe uma mensagem u ∈ Zn k , tal que a Equação 2.15 é satisfeita. Exemplo 2.2.8 Considere um código C com parâmetros (5, 3) e matriz geradora dada por (2.17). Suponha que v = (00101) seja a mensagem recebida e queremos identificar a mensagem enviada u = (u1u2u3) tal que (u1u2u3) ·  1 0 1 1 1 0 1 0 1 1 0 0 1 0 1  = (00101). 26 Pela multiplicação, temos um sistema linear com 3 incógnitas e 5 equações u1 = 0; u2 = 0; u1 + u3 = 1; u1 + u2 = 0; u1 + u2 + u3 = 1. . Podemos observar que u1 = 0 e u2 = 0. Então u1 + u3 = 1; 0 + u3 = 1. . Portanto, u3 = 1, deste modo, a mensagem enviada foi u = (001). Este método, não é a melhor maneira de decodificar um canal, uma alternativa mais eficiente é utilizar G na sua forma padrão, de modo que apenas observando o início das palavras é possível realizar a decodificação da mensagem. Definição 2.2.7 Uma matriz geradora G de um código C está na forma padrão (ou sistemática) se G = (Ik|P), (2.18) em que Ik é a matriz identidade de ordem k e P é uma matriz de ordem k × (n− k). Exemplo 2.2.9 Considere um código C com parâmetros (5, 3) e matriz geradora G dada por (2.17). Para definir a matriz geradora em sua forma padrão é necessário realizar algumas operações ele- mentares e permutações em suas colunas, de modo a resultar na matriz em sua forma sistemática. Realizando tais operações, a matriz resultante G′ na forma sistemática será G′ =  1 0 0 1 0 0 1 0 1 1 0 0 1 0 1  . Desta forma, as três primeiras colunas são correspondentes à I3 e as duas últimas à P . Definição 2.2.8 Considere C um código de parâmetros (n, k). Se G = (Ik|P) é uma matriz geradora de C na forma padrão, então H = (−P t|In−k) é chamada de matriz controle de paridade de C, onde P t é a matriz transposta de P de ordem (n− k)× k e, In−k a matriz identidade de ordem n− k. Esta matriz H é utilizada para verificar se uma mensagem pertence ou não ao código. Isto é realizado pela multiplicação da matriz H pela mensagem recebida, se a mesma for igual a 0, então é palavra código, caso contrário não é palavra código. Como podemos observar a seguir G ·H t = (Ik|P) · (−P t|In−k) = −P + P = 0, se v ∈ C, então, 27 v = u ·G −→ v ·H t = u · (G ·H t) = 0, deste modo, v é uma palavra código. Exemplo 2.2.10 Seja C um código com parâmetros (5, 3) e matriz geradora G dada por G =  1 0 0 1 0 0 1 0 1 1 0 0 1 0 1  . Queremos verificar se as mensagens recebidas, v1 = (10111) e v2 = (00010) são palavras código. Observa-se que a matriz G encontra-se na sua forma padrão, então podemos determinar a matriz H , de modo que H = ( 1 1 0 1 0 0 1 1 0 1 ) . Vamos verificar se v1 = (10111) é uma palavra código de C. Multiplicando v1 por H t v1 ·H t = (10111) ·  1 0 1 1 0 1 1 0 0 1  = (00). Como a multiplicação resultou em um vetor nulo, então v1 ∈ C. Agora, vamos verificar se v2 = (00010) é uma palavra código de C. Multiplicando v2 por H t v2 ·H t = (00010) ·  1 0 1 1 0 1 1 0 0 1  = (10). Como a multiplicação não resultou em um vetor nulo, então v2 /∈ C. 28 3 CÓDIGOS CONVOLUCIONAIS Neste capítulo, abordaremos os códigos convolucionais, que são códigos corretores de erros amplamente utilizados pela sua baixa complexidade de implementação tanto do codificador quanto decodificador e, pela fácil adaptação da taxa de codificação. Na Seção 3.1 serão apresentados os métodos de codificação deste código e na Seção 3.2 será apresentada a decodificação baseada no algoritmo de Viterbi. As definições apresentadas neste capítulo podem ser encontradas em [FORNEY 1970, OMURA 1969, ISCAN, LENTNER e XU 2016, TAHIR, SCHWARZ e RUPP 2017, SYBIS et al. 2016]. 3.1 CODIFICAÇÃO Um código convolucional utiliza de memórias finitas no codificador para gerar uma redundância, [FORNEY 1970]. Este código é definido através dos parâmetros (n, k,M), onde n é o número de bits produzidos na saída, k o número de bits inseridos na entrada e M a quantidade de memórias no codificador. Um código com estes parâmetros pode ser caracterizado por uma máquina de estados. Na Figura 7 podemos observar a máquina de estados de um código convolucional com parâmtros (1, 1, 2), onde cada retângulo representa uma memória do codificador e este código possui apenas uma entrada e uma saída. Figura 7 – Máquina de estados (1,1,2). Entrada Saída Fonte: Próprio autor. Um esquema simplificado para codificação convolucional pode ser visto na Figura 8. Figura 8 – Esquema simplificado da codificação convolucional. DEMUX MUXCODIFICAÇÃO u v Fonte: Próprio autor. Se a sequência de entrada k de informação no codificador a cada iteração tn é dada por u = (u10u 2 0 . . . u k 0u 1 1u 2 1 . . . u k 1 . . . u 1 tnu 2 tn . . . u k tn), (3.1) e a sequência codificada n na saída a cada iteração tn é v = (v10v 2 0 . . . v n 0 v 1 1v 2 1 . . . v n 1 . . . v 1 tnv 2 tn . . . v k tn), (3.2) 29 onde a entrada u é demultiplexada em k entradas e as n saídas são multiplexadas em v, então existe uma sequência geradadora para as memórias do codificador dada por gi = (gi0g i 1 . . . g i M), (3.3) onde i = 1, . . . , n. Estas sequências geradoras são também chamadas de resposta ao impulso e podem ser determinadas aplicando 1’s e 0’s para cada caminho em cada memória do codificador, onde 1 significa conexão e 0 não conexão. Exemplo 3.1.1 Considere o código convolucional (2,1,7) com máquina de estados como da Figura 9. Figura 9 – Máquina de estados código convolucional (2,1,7). u 1 2 v v Fonte: Próprio autor. Neste caso, os geradores ou resposta ao impulso deste código serão dados por g1(10000101), g2(10101011). A codificação de um código convolucional pode ser realizada de várias formas, dentre elas: polinômio gerador, matriz geradora, convolução, diagrama de estados ou diagrama de treliça. A seguir, apresentaremos tais formas. • Polinômio Gerador Seja gj = (gj0g j 1...g j m), (3.4) com j = 1, . . . , n, uma sequencia geradora de um código convolucional (n, k,M), onde o correspondente polinômio gerador para cada j é gj(D) = gj0 + gj1D + gj2D 2 + · · ·+ gjMD M , (3.5) onde D é a variável de atraso unitário. Se u é uma mensagem a ser codificada e u(D) o polinômio que representa u, então as sequências codificadas serão dadas por 30 v1(D) = u(D)g1(D), v2(D) = u(D)g2(D), . . . vn(D) = u(D)gn(D), que serão multiplexadas na palavra-código v = (v1v2 . . . vn). Exemplo 3.1.2 Considerando o código convolucional (2,1,7) com máquina de estados como da Figura 9, vamos codificar a mensagem u = (1010011). Representando as sequências geradoras e a mensagem em polinômios geradores temos que g1(D) = 1 +D5 +D7, g2(D) = 1 +D2 +D4 +D6 +D7, u(D) = 1 +D2 +D5 +D6. Deste modo para v1(D) v1(D) = g1(D)u(D) = (1 +D5 +D7)(1 +D2 +D5 +D6) = 1 +D2 +D6 +D9 +D10 +D11 +D12 +D13. Portanto, v1 = (10100010011111). Do mesmo modo para v2(D) v2(D) = g2(D)u(D) = (1 +D2 +D4 +D6 +D7)(1 +D2 +D5 +D6) = 1 +D5 +D6 +D10 +D11 +D13. E, assim, v2 = (10000110001101). Logo, multiplexando, v = (v1v2) = (1100100000011100001011111011). • Matriz Geradora Para este método de codificação, uma matriz geradora é utilizada, esta matriz é construída a partir das sequências geradoras gj = (gj0g j 1 . . . g j M), com j = 1, . . . , n, de um código convolucional (n, k,M). Cada linha da matriz geradora é formada por uma réplica da sequência geradora e cada nova linha é deslocada uma posição para a direita e bits zero são adicionados nas lacunas. 31 Assim, a matriz geradora tem a seguinte forma G =  G0 G1 . . . GM 0 0 0 0 G0 G1 . . . GM 0 0 0 0 G0 G1 . . . GM 0 0 0 0 G0 G1 . . . . . .  , (3.6) onde a dimensão da matriz depende do comprimento da mensagem. Por exemplo, para um código convolucional (2, 1, 2), temos que os polinômios geradores tem a seguinte forma g1 = (g10g 1 1g 1 2), (3.7) e, g2 = (g20g 2 1g 2 2). (3.8) Assim, a matriz geradora será dada por G =  g10g 2 0 g11g 2 1 g12g 2 2 0 0 0 0 g10g 2 0 g11g 2 1 g12g 2 2 0 0 0 0 g10g 2 0 g11g 2 1 g12g 2 2 0 0 0 0 g10g 2 0 g11g 2 1 . . .  . (3.9) Casos onde existe mais de uma saída, Gi será a concatenação de gji , para cada i = 1, . . . ,M e j = 1, . . . , n. A codificação, também pode ser realizada utilizando a Equação 2.15. Exemplo 3.1.3 Considerando o código convolucional (2,1,7) com máquina de estados como da Figura 9, vamos codificar a mensagem u = (1010011). Sabendo que as sequências geradoras são dados por g1 = (10000101) e g2 = (10101011). A matriz G terá a forma G =  11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11  . Para codificar pela matriz geradora basta efetuar a multiplicação da mensagem pela matriz 32 geradora, como em (2.15), da seguinte forma v = uG = (1010011)  11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11 00 00 00 00 00 00 00 11 00 01 00 01 10 01 11  . Logo, v = (1100100000011100001011111011) • Convolução A codificação por convolução de dois sinais u e g é dada por v(i) = (u ∗ g)(i) = i∑ j=0 u(j)g(j − i). (3.10) Exemplo 3.1.4 Considerando o código convolucional (2,1,7) com máquina de estados como da Figura 9, vamos codificar a mensagem u = (1010011), sabendo que as geradoras são dados por g1 = (10000101) e g2 = (10101011). Para v1 = u ∗ g1, temos v1 = (1010011) ∗ (10000101), que pode ser calculada fazendo∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 ∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣ . 33 Portanto, v1 = (10100010011111). Do mesmo modo para v2 = u ∗ g2, tem-se que v2 = (1010011) ∗ (10101011) = (10000110001101). Logo, v = (v1v2) = (1100100000011100001011111011). • Diagrama de Estados As operações realizadas por uma máquina de estados podem ser descritas por um diagrama de estados. Em um diagrama de estados podemos observar todos os estados da máquina do código convolucional em questão, os quais podem ser representados por circulos, e as possíveis transições, representadas por setas, tal que A/BB, onde A representa o bit atual que está sendo inserido na máquina e BB representa a saída do codificador, como pode ser observado na Figura 10. Figura 10 – Representação diagrama de estados. m A/BB Fonte: Próprio autor. Exemplo 3.1.5 Considere o código convolucional (2, 1, 3) com máquina de estados como o da Figura 11. Figura 11 – Máquina de estados código convolucional (2,1,3). u 1 2 v v Fonte: Próprio autor. Podemos representar seu diagrama de estados como na Figura 12. 34 Figura 12 – Diagrama de estados código convolucional (2,1,3). 000 100 001 010 101 011 110 111 1/11 1/00 1/10 1/00 0/10 0/00 0/11 1/11 1/010/01 0/11 0/01 1/01 0/10 1/10 0/00 Fonte: Próprio autor. Para codificar a mensagem u = (10111), devemos partir do estado inicial da máquina, ou seja, com memória 000, e realizar as transições com a inserção de cada bit. Podemos observar as transições realizadas pela Figura 13 , onde a sequência de saltos realizados é dado por A, B, C, D, E, F, G e H, respectivamente. Vale ressaltar, que na codificação de um código convolucional é necessário sempre limpar a memória da máquina, ou seja, voltar ao estado inicial da máquina, para isto, são inseridos M bits zero, após toda a mensagem ser inserida. Figura 13 – Codificação da mensagem u = (10111). 000 100 001 010 101 011 110 111 1/00 1/010/01 1/011/11 A B C D E 0/00 0/01 0/11 F G H Fonte: Próprio autor. Deste modo, temos que v = (1101000101010011). • Diagrama de Treliça O diagrama de treliça permite observar, para cada instante tn, todas as transições possíveis de estados. Cada uma das colunas deste diagrama representa todos os estados da máquina e suas conexões. Este diagrama pode ser utilizado tanto na codificação, quanto na decodificação. Para um código (n, k,M), se o tamanho da mensagem a ser codificada é k, então serão utilizadas (k +M) cópias da treliça, pois cada cópia representa um bit de entrada e como as memórias do codificador devem sempre voltar para seu estado inicial, serão adicionadas M cópias da treliça para limpar as memórias. 35 Exemplo 3.1.6 Considerando o código do Exemplo 3.1.5 e partindo da máquina de estados da Figura 11, pode-se representar seu diagrama de treliça como na Figura 14. Figura 14 – Diagrama de treliça código convolucional (2,1,3). 000 100 001 010 101 011 110 111 1/11 1/00 1/10 1/00 0/10 0/00 0/11 1/11 1/01 0/01 0/11 0/01 1/01 0/10 1/10 0/00 Fonte: Próprio autor. Vamos codificar a mensagem u = (10111) utilizando o diagrama de treliça. Para isso, devemos partir do estado inicial da máquina, ou seja, com memória 000, e realizar as transições com a inserção de cada bit. Podemos observar as transições realizadas pela Figura 15, onde após inserirmos os bits da mensagem, foram inseridos 3 bits 0 para limpar a memória do codificador. Figura 15 – Codificação da mensagem u = (10111). 000 100 001 010 101 011 110 111 1/11 1/10 1/00 0/01 0/11 0/01 1/01 0/00 t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 Fonte: Próprio autor. 36 Deste modo, temos que v = (1101000101010011). 3.2 DECODIFICAÇÃO A decodificação mais utilizada para códigos convolucionais, é a baseada no algoritmo de Viterbi, que é uma técnica de decodificação por máxima verossimilhança (Maximum Likelihood Decoding). O funcionamento da decodificação por máxima verossimilhança baseia-se em comparar a soma das distâncias de Hamming, entre todos os dados da sequência de bits recebidos no receptor e todos os dados de cada uma das possíveis sequências que podem ser geradas no codificador convolucional do transmissor. A menor soma destas distâncias indica a possível sequência de dados que provavelmente teria sido gerada pelo codificador convolucional do transmissor. Seja m uma mensagem e c uma palavra-código correspondente obtida através de um codificador que será transmitida por um canal discreto sem memória. A mensagem recebida r pode ser diferente de c devido a ruídos inseridos no canal. A partir de r o decodificador gera uma estimativa ĉ que é equivalente a uma estimativa da mensagem m̂. Idealmente c = ĉ e m = m̂, caso contrário ocorreu um erro de decodificação. Para que a decodificação seja ótima a probabilidade de erro deve ser minimizada e isto ocorre quando a função de verossimilhança é maximizada. Se p(r|c) é a probabilidade de receber uma mensagem r dado que c foi enviado, deste modo a função de verossimilhança será dada por log(p(r|c)). Seja um canal BSC, com duas possíveis entradas (1 ou 0), que são igualmente afetadas por erro, com probabilidade p, temos que p(0|0) = 1− p = p(1|1) e p(0|1) = p = p(1|0). Se uma palavra-código c é transmitida por este canal e r é a mensagem recebida, ambas com mesmo comprimento n, então p(r|c) = n∏ i=1 p(ri|ci). (3.11) A função de verossimilhança será log p(r|c) = log ( n∏ i=1 p(ri|ci) ) = n∑ i=1 log(p(ri|ci)). (3.12) Sabendo que p(ri|ci) = { p, se ri 6= ci 1− p, se ri = ci , (3.13) que a distância de Hamming é dada por d = dh(c, r) = #{i | ri 6= ci}, (3.14) 37 onde # representa cardinalidade, e supondo que r difere de c em d posições, então log(p(r|c)) = d log(p) + (n− d) log(1− p) = d log ( p 1− p ) + n log(1− p). (3.15) Podemos observar que n log(1 − p) é constante, pois só depende da probabilidade de erro e do tamanho da palavra recebida. Como usualmente p < 1/2, então log ( p 1−p ) < 0. Assim, um decodificador de máxima verossimilhança é aquele que a estimativa ĉ é escolhida com base na menor distância de Hamming entre o vetor recebido r e a palavra-código c transmitida. Exemplo 3.2.1 Considere c1 = (0000110111) e c2 = (1101000111) duas palavras-código de um código convolucional de parâmetro (2, 1, 2). Supondo que a palavra recebida pelo decodificador é r = (1001110111), vamos determinar a estimativa ĉ no receptor por máxima verossimilhança. Como o decodificador por máxima verosimilhança determina a palavra-código pela menor distância de Hamming entre a palavra recebida e a possível palavra-código, temos que a distância de Hamming para c1 e c2 são dadas por dh(r, c1) = 2, dh(r, c2) = 3. Logo, por máxima verossimilhança fazemos ĉ = c1 3.2.1 Algoritmo de Viterbi O decodificador convolucional de Viterbi tem seu funcionamento baseado no conceito do dia- grama de treliça, onde todas as possíveis transições entre todos os possíveis estados do codificador convolucional, localizado no transmissor, podem ser representados ao longo do tempo. Para estimar ĉ a partir de uma mensagem r recebida por um codificador convolucional (n, k,M), as seguintes etapas são realizadas na decodificação: 1. Partindo do estado inicial da treliça, compara-se a saída de cada possível transição com os bits recebidos, calculando a distância de Hamming. 2. Soma-se a distância de Hamming entre os bits recebidos e as possíveis saídas e cada transição. 3. Esta operação é realizada até dois caminhos convergirem para um mesmo estado. O caminho que irá continuar é aquele com a menor distância de Hamming acumulada até o momento. 4. Estas operações são realizadas até terminarem os dados recebidos. Vários caminhos podem chegar ao final, mas o escolhido será aquele com a menor distância acumulada. Assim, considerando todos os possíveis caminhos percorridos por r, a mensagem ĉ mais provável será aquela com a menor distância de r. 38 Exemplo 3.2.2 Considere o código convolucional (2,1,2) com diagrama de treliça como da Figura 16. Vamos decodificar a mensagem r = (1001110111) utilizando o algortimo de Viterbi. Figura 16 – Diagrama de treliça código convolucional (2,1,2). 00 01 10 11 0/11 0/00 0/01 0/10 1/11 1/00 1/10 1/01 Fonte: Próprio autor. A Figura 17 foi construída seguindo os passos realizados pelo algoritmo de Viterbi. Figura 17 – Decodificação utilizando o algoritmo de Viterbi. 00 01 10 11 1/11 1/00 1/10 10 01 11 01 11 0/00 0/00 0/00 0/00 0/00 1/11 1/11 0/01 0/01 0/01 1/01 1/10 0/11 0/11 0/11 0/10 0/10 1 1 1 1 2 2 1 1 2 2 3 3 4 2 1 3 3 3 4 4 3 2 3 1 2 4 2 5 2 2 4 2 2 Fonte: Próprio autor. Podemos observar que o caminho com a menor distância de Hamming possui um valor de d = 2, e este será o caminho para o qual o decodificador irá escolher a palavra-código ĉ. Na Figura 18 pode-se observar o caminho escolhido pelo decodificador. Figura 18 – Caminho escolhido pela decodificação utilizando o algoritmo de Viterbi. 00 01 10 11 10 01 11 01 11 0/00 0/00 0/01 0/11 1 1 2 2 3 2 2 2 2 2 2 1/11 Fonte: Próprio autor. 39 Assim, temos que ĉ = (0000110111) e m̂ = (001). No Capítulo 5 será realizada uma implementação computacioanal dos códigos convolucionais, a máquina de estados da Figura 9 será utilizada para implementação, a codificação será baseada no diagrama de treliça e a decodificação no algoritmo de Viterbi. Esta implementação tem como objetivo observar o desempenho deste código na detecção e correção de erros, assim como sua latência e throughput. 40 4 CÓDIGOS POLARES Neste capítulo, apresentaremos os códigos polares, que são códigos de bloco introduzidos por Arikan, [ARIKAN 2009]. Estes códigos são construídos a partir de uma estratégia proposta também por Arikan chamada de polarização de canal, onde cópias de um canal discreto sem memória são combinadas de modo que, após divididas, podem ser separados em canais bons e ruins. Deste modo, bits de informação são enviados nos canais confiáveis (bons) e bits congelados nos canais mais ruidosos (ruins). Na Seção 4.1 será apresentada a estratégia de polarização de canal que auxilia na codificação deste código, na Seção 4.2 serão apresentados os métodos de codificação e na Seção 4.3 a decodificação dos códigos polares. As definições apresentadas neste capítulo podem ser encontradas em [ARIKAN 2009, TAHIR, SCHWARZ e RUPP 2017, OLIVEIRA e LAMARE 2017, ISCAN, LENTNER e XU 2016, SYBIS et al. 2016, HUIGOL 2017, NIU et al. 2014, SARKIS e GROSS 2013a, SARKIS e GROSS 2013b, LEROUX et al. 2011]. 4.1 POLARIZAÇÃO DE CANAL Seja um canal sem memória W : X → Y , com probabilidade de transição W (Y |x) = P (Y = y|X = x). (4.1) Vamos considerar N cópias do canal W, representado por WN : XN → Y N , (4.2) onde XN = (X1, X2, ..., XN) e Y N = (Y1, Y2, ..., YN), com probabilidade de transição dada por WN(yN 1 |xN 1 ) = N∏ i=1 W (yi|xi), (4.3) onde xN 1 = (x1, x2, ..., xN), e yN 1 = (y1, y2, ..., yN). A capacidade do canal W , que iremos denotar I(W), representa como visto na Definição 2.1.6, a maior taxa que a comunicação alcança com W e pode 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) ) . (4.4) Agora, iremos realizar a combinação de N canais, de modo que, WN : XN → Y N , onde, N = 2n, n ≥ 0 com n ∈ Z+. • Canal N = 1 41 Inicialmente para N = 1, teremos somente a cópia de um único canal, que pode ser representado pela Figura 19. Figura 19 – Canal sem memória. x y W Fonte: Próprio autor. • Canal N = 2 Para N = 2, teremos a combinação de dois canais W, W2 : X 2 → Y 2, (4.5) nesta combinação na entrada dos canais teremos x1 e x2 e na saída y1 e y2, como representado na Figura 20 Figura 20 – Canal para N = 2. x 1 x 2 y 1 y 2 u 1 u 2 W W Fonte: Próprio autor. Podemos observar que diferente do canal W1, no canal W2 temos uma operação de soma antes da entrada x1. Deste modo, mapeando as entradas x1 e x2 a partir de u1 e u2, temos que, x1 será a soma entre as entradas u1 e u2 e x2 será a própria entrada u2. Assim, as probabilidades de transição do canal W2 serão obtidas por essas combinações W2(y1, y2|u1, u2) = W (y1|u1 ⊕ u2)W (y2|u2). (4.6) A partir disso conseguimos mapear as entradas x = (x1, x2) a partir de u = (u1, u2) e uma matriz geradora dada por essas combinações. Deste modo x2 1 = u2 1G2, (4.7) onde G2 é a matriz geradora dada a partir de W2. G2 = ( 1 0 1 1 ) . (4.8) 42 • Canal N = 4 Para N = 4, teremos a combinação de quatro canais W, ou a combinação de duas cópias de W2 como representado pela Figura 21. Para esta construção temos 4 entradas x e 4 saídas y, de modo que W4 : X 4 → Y 4. (4.9) Figura 21 – Canal para N = 4. x 1 x 2 x 3 x 4 y 1 y 2 y 3 y 4 u 1 u 2 u 3 u 4 W 2 W 2 W W W W R 4 v 1 v 2 v 3 v 4 s 1 s 2 s 3 s 4 Fonte: Próprio autor. Entretanto para N = 4, será necessário fazer uma operação de permutação para a combinação dos canais, como mostrado na Figura 21. Está permutação é representada por Rn e irá separar as entradas de índices ímpares das pares. O vetor de entrada u4 1 = (u1, u2, u3, u4) em W4, é transformado primeiramente em s41 = (s1, s2, s3, s4) de tal forma que s2i−1 = u2i−1 ⊕ u2i e s2i = u2i, para 1 < i < 4. Após, o operador R4 age sobre o vetor s41, de modo s41 = (s1, s2, s3, s4)→ v4 1 = (s1, s3, s2, s4), (4.10) que também pode ser representado por R4 =  1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1  . (4.11) 43 As probabilidades de transição do canal serão obtidas da seguinte forma W4(y4 1|u4 1) = W2(y2 1|u1 ⊕ u2, u3 ⊕ u4)W2(y4 3|u2, u4). (4.12) Deste modo temos que x4 1 = u4 1G4, (4.13) onde G4 é dada pela seguinte matriz G4 =  1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1  . (4.14) • Canal N = 8 Para N = 8, teremos a combinação de oito canais W, ou a combinação de duas cópias de W4 como representado pela Figura 22. Para esta construção temos 8 entradas x e 8 saídas y, de modo que W8 : X 8 → Y 8. (4.15) Assim como no caso N = 4, será necessário fazer uma operação de permutação para a combina- ção dos canais, como representado na Figura 22. O vetor de entrada u8 1 = (u1, u2, u3, u4, u5, u6, u7, u8) é transformado primeiramente em s81 = (s1, s2, s3, s4, s5, s6, s7, s8) de tal forma que s2i−1 = u2i−1 ⊕ u2i e s2i = u2i, para 1 < i < 8. Após, o operador R8 age sobre o vetor s81, de modo s81 = (s1, s2, s3, s4, s5, s6, s7, s8)→ v8 1 = (s1, s3, s5, s7, s2, s4, s6, s8). (4.16) A matriz permutação R8 será representada da seguinte forma: 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  . (4.17) 44 Figura 22 – Canal para N = 8. x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 R 8 W 2 W 2 W 2 W 2 W W W W W W W W R 4 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 R 4 s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8 Fonte: Próprio autor. As probabilidades de transição do canal serão obtidas da seguinte forma W8(y8 1|u8 1) = W (y4 1|u1 ⊕ u2, u3 ⊕ u4, u5 ⊕ u6, u7 ⊕ u8)W (y8 5|u81,e). (4.18) Deste modo temos que x8 1 = u8 1G8, (4.19) 45 onde G8 é dada 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  . (4.20) • Caso Geral - WN Para a construção do canal geral, temos N vetores de entrada xN 1 e N vetores de saída yN 1 . A Figura 23 representa este canal. Como podemos observar, existe um bloco representado pela matriz de permutação RN e depois duas cópias independentes de WN/2. Figura 23 – Canal geral WN . u 1 2 . . . N/2 N/2 - 1 . . . u u u N/2 + 2 N/2 + 1 u u N - 1 u N u s 1 2 N/2 N/2 - 1 s s s N/2 + 2 N/2 + 1 s s N - 1 s N s . . . . . . v 1 2 N/2 N/2 - 1 v v v N/2 + 2 N/2 + 1 v v N - 1 v N v . . . . . . y 1 2 N/2 N/2 - 1 y y y N/2 + 2 N/2 + 1 y y N - 1 y N y . . . . . . N/2 W N/2 W N R Fonte: Próprio autor. A matriz de permutação RN faz com que as entradas ímpares sejam as entradas da primeira cópia de WN/2, enquanto que, as entradas pares sejam as entradas da segunda cópia de WN/2. Para o vetor de entrada uN 1 em WN , ele é 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 vN 1 = (s1s3, ..., sN−1, s2s4, ..., sN) que se 46 tornarão as entradas para as duas cópias de WN/2. Utilizando RN pode-se mapear os vetores de entrada xN 1 a partir dos vetores uN 1 a partir de uma matriz geradora GN da seguinte forma xN 1 = uN 1 GN . (4.21) A divisão de canal tem como objetivo separar os canaisWN emN canaisW por grau de polarização, a fim de observar quais canais possuem maior ou menor confiabilidade. Deste modo W i N : X → Y N ×X i−1, (4.22) onde, 1 ≤ i ≤ N . As probabilidades de transição podem ser definidas por W i N(y N 1 ,u i−1 1 |ui) = ∑ uN i+1∈XN−1 1 2N−1 WN(yN 1 |uN 1 ), (4.23) onde, ui representa a entrada e (yN 1 ,u i−1 1 ) a saída de W i N . Calcular as probabilidades de transição (4.23) de modo a obter a capacidade de canal para um canal qualquer não é simples. Porém, considerando um canal BEC com probabilidade de apagamento e = 1/2, em [ARIKAN 2009] foi apresentada uma fórmula fechada para o cálculo da capacidade para cada N . Neste caso, a capacidade I(WN) pode ser calculada de maneira recursiva por I(W 2i−1 N ) = I(WN/2) 2 (4.24) e I(W 2i N ) = 2I(WN/2)− I(WN/2) 2, (4.25) com I(W1) = 1− e. Por facilidade de notação os canais bons serão representados por W+ e os ruins por W−. Exemplo 4.1.1 Considerando canais BEC com e = 1/2, vamos calcular as capacidades destes canais utilizando a polarização de canal para diferentes valores de N . • N = 1 Temos neste caso que I(W ) = 1− e = 1− 0.5 = 0.5. Figura 24 – I(W1). yx W Fonte: Próprio autor. 47 • N = 2 A capacidade total será dividida em dois canais, W− e W+, como pode ser observado na Figura 25. Figura 25 – I(W2). 1 u 2 u x 1 x 2 W W 1 y 2 yW - W + Fonte: Próprio autor. Aplicando as Equações (4.24) e (4.25), temos I(W−) = I(W )2 = (0.5)2 = 0.25, I(W+) = 2I(W )− I(W )2 = 1− (0.5)2 = 0.75. A maior capacidade representa aquele canal que possui uma confiabilidade maior, e é dado por aquele canal que possui mais combinações, no caso, u1. • N = 4 A capacidade total será novamente dividida, entretanto agora entre 4 canais, como na Figura 26. Figura 26 – I(W4). u 1 u 2 u 3 u 4 W -- W -+ W +- W ++ x 1 x 2 x 3 x 4 W W W W 1 y 2 y 3 y 4 yW - W + W - W + Fonte: Próprio autor. 48 Os canais serão calculados da seguinte forma I(W−−) = I(W−)2 = (0.25)2 = 0.0625 I(W−+) = 2I(W−)− I(W−)2 = 2(0.25)− (0.25)2 = 0.4375 I(W+−) = I(W+)2 = (0.75)2 = 0.5625 I(W++) = 2I(W+)− I(W+)2 = 2(0.75)− (0.75)2 = 0.9375. Neste caso podemos observar a elevada diferença de confiabilidade entre canais, poderíamos, por exemplo, congelar a entrada u1 e transmitir as informações pelas entradas u2, u3 e u4. • N = 8 Neste caso a capacidade será novamente dividida entre 8 canais, como na Figura 27. Figura 27 – I(W8). W ---u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 W --+ W -+- W -++ W +-- W +-+ W ++- W +++ W -- W -+ W +- W ++ W -- W -+ W +- W ++ W - W + W - W + W - W + W - W + W W W W W W W W Fonte: Próprio autor. 49 Analogamente aos casos anteriores, as capacidades serão I(W−−−) = I(W−−)2 = (0.0625)2 = 0.0039 I(W−−+) = 2I(W−−)− I(W−−)2 = 2(0.0625)− (0.0625)2 = 0.1210 I(W−+−) = I(W−+)2 = (0.4375)2 = 0.1914 I(W−++) = 2I(W−+)− I(W−+)2 = 2(0.4375)− (0.4375)2 = 0.6835 I(W+−−) = I(W+−)2 = (0.5625)2 = 0.3164 I(W+−+) = 2I(W+−)− I(W+−)2 = 2(0.5625)− (0.5625)2 = 0.8085 I(W++−) = I(W++)2 = (0.9375)2 = 0.8789 I(W+++) = 2I(W++)− I(W++)2 = 2(0.9375)− (0.9375)2 = 0.9960. Neste caso, para uma transmissão de 4 bits de informação poderíramos congelar as entradas u1, u2, u3 e u5 e transmitir as informações pelas entradas u4, u6, u7 e u8 Os cálculos para a confiabilidade dos canais podem ser realiados para N = 2n, e quanto maior o valor de n, ou seja, com n→∞, os canais polarizados vão para os extremos 0 e 1. Podemos observar pela Figura 28 uma simulação que realizamos para vários valores de N . Nela os canais bons são aqueles que possuem mais combinações entre os canais e maior informação mútua, já os canais ruins possuem menos combinações e uma informação mútua menor. Figura 28 – Canais polarizados. Fonte: Próprio autor. 50 4.2 CODIFICAÇÃO Vimos na Seção 4.1 que para N = 2n com n ≥ 0, a codificação de canal de um vetor de entrada uN 1 em xN 1 pode ser realizada a partir de uma matriz geradora GN como em (4.21). A partir da polarização de canal podemos decidir quais serão os canais de informação e quais serão os canais congelados. Com esta informação, separamos as linhas da matriz GN em dois conjuntos, o conjunto A representando as linhas da matriz relacionadas com os bits de informação e Ac representando as linhas relacionadas com os bits congelados. Do mesmo modo, a divisão do vetor uN 1 é realizada, divindo uN 1 em uA que indica o vetor com os bits de informação e uAc que indica o vetor com os bits congelados. Assim, a codificação será dada por xN 1 = uAGN(A) ⊕ uACGN(A c), (4.26) onde GN(A) é a submatriz formada pelas linhas da matriz GN com índices A e GN(Ac) é a submatriz formada pelas linhas da matriz GN com índices Ac. Deste modo, definimos um código polar como um código de bloco representado pelos parâmetros (N, k,A, µAC ), onde N é o comprimento da palavra-código xN 1 produzida, k a dimensão do código que especifica o tamanho de A, A são as linhas de GN que representam os bits de informação que serão transmitidos e µAC são os bits dos canais congelados. Exemplo 4.2.1 Considere o código polar com parâmetros (4, 2, {1,3}, (1,0)). Utilizando a matriz G4 dada em (4.14), a codificação será realizada da seguinte forma x4 1 = (u1u3) [ 1 0 0 0 1 1 0 0 ]⊕ (10) [ 1 0 1 0 1 1 1 1 ] . Sabendo que (u1, u3) são entradas binárias, existem 4 combinações possíveis (0, 0), (0, 1), (1, 0), (1, 1). Sendo assim, substitui-se cada uma delas em (u1, u3) e encontramos os seguintes valores para x4 1 (0, 0)→ x4 1 = (0, 0, 0, 0) ⊕ (1, 0, 1, 0) = (1, 0, 1, 0); (0, 1)→ x4 1 = (1, 1, 0, 0) ⊕ (1, 0, 1, 0) = (0, 1, 1, 0); (1, 0)→ x4 1 = (1, 0, 0, 0) ⊕ (1, 0, 1, 0) = (0, 0, 1, 0); (1, 1)→ x4 1 = (0, 1, 0, 0) ⊕ (1, 0, 1, 0) = (1, 1, 1, 0). Veremos a seguir que a matriz geradora GN pode ser determinada utilizando expressões algébricas, que são baseadas no produto de Kronecker de matrizes. O produto de Kronecker, representado por ⊗, é uma operação realizada entre duas matrizes, A’ com dimensão m x n e B’ com dimensão p x q, da seguinte forma A′ ⊗B′ =  a′11B ′ . . . a′1nB ′ ... . . . ... a′m1B ′ . . . a′mnB ′  . (4.27) 51 Ou seja A′ ⊗B′ =  a′11B ′ 11 a′11B ′ 12 . . . a′1nB ′ 11 a′1nB ′ 12 a′11B ′ 21 a′11B ′ 22 . . . a′1nB ′ 21 a′1nB ′ 22 ... ... . . . ... ... a′m1B ′ 11 a′m1B ′ 12 . . . a′mnB ′ 11 a′mnB ′ 12 a′m1B ′ 21 a′m1B ′ 22 . . . a′mnB ′ 21 a′mnB ′ 22  . (4.28) Exemplo 4.2.2 Considere a matriz F = [ 1 0 1 1 ] . (4.29) Vamos determinar o produto de Kronecker F⊗n, onde F⊗n = F ⊗ F⊗(n−1), para n = 1, 2, 3 e considerando que F⊗0 = 1. • Para n = 1 temos que o produto de Kronecker é dado da seguinte forma F⊗1 = F ⊗ F⊗0. Assim, F⊗1 = F ⊗ [1] = [ 1 0 1 1 ] . • Para n = 2 temos que F⊗2 = F ⊗ F⊗1 =  1 ∗ ( 1 0 1 1 ) 0 ∗ ( 1 0 1 1 ) 1 ∗ ( 1 0 1 1 ) 1 ∗ ( 1 0 1 1 )  =  1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1  . • Para n = 3 temos F⊗3 = F ⊗ F⊗2 =  1 ∗  1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1  0 ∗  1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1  1 ∗  1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1  1 ∗  1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1   52 =  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, veremos como obter GN utilizando o produto de Kronecker de matrizes. Seja o canal W2 apresentado na Figura 20 com matriz geradora G2 dada por (4.8). Por facilidade de notação iremos considerar F = G2. (4.30) Assim, para o canal W4 apresentando na Figura 21, a matriz geradora G4 dada em (4.14), pode ser calculada por G4 = (I2 ⊗ F )R4(I2 ⊗ F ), (4.31) onde I2 é a matriz identidade de ordem 2 e R4 a matriz permutação dada em (4.11). Para o canal W8 apresentando na Figura 22 com matriz G8 dada em (4.20), temos que G8 = (I4 ⊗ F )R8(I2 ⊗G4), (4.32) onde I4 é a matriz identidade de ordem 4 e R8 é a matriz de permutação dada em (4.17). Procedendo de modo análogo, a matriz geradoras GN para um canal WN dado em Figura 23, pode ser obtida através da relação GN = (IN/2 ⊗ F )RN(I2 ⊗GN/2). (4.33) A combinação de canal pode ser alterada, de modo a obter uma simplificação na expressão da matriz geradora. Algebricamente, esta simplificação significa realizar as seguintes manipulações em (4.33) GN = (IN/2 ⊗ F )RN(I2 ⊗GN/2) = RN(F ⊗ IN/2)(I2 ⊗GN/2) = RN(F ⊗GN/2). Substituindo GN/2 = RN/2(F ⊗GN/4) temos GN = RN(F ⊗ (RN/2(F ⊗GN/4))) = RN(I2 ⊗RN/2)(F ⊗2 ⊗GN/4). 53 Substituindo GN/4 e sucessivamente até chegar em G2 = F teremos GN = BNF ⊗n, (4.34) onde BN = RN(I2 ⊗BN/2) = RN(I2 ⊗RN/2)(I4 ⊗RN/4) . . . (IN/2 ⊗R2). Enquanto a matriz de permutação RN opera como um operador de embaralhamento que mapeia as entradas do canal, a matriz de permutação BN opera como um operador inversor de bits nas posições dos vetores de entrada. Conforme N aumenta, BN fará cada vez mais trocas nas posições dos vetores. Exemplo 4.2.3 Para N = 4, temos que B4 = R4(I2 ⊗R2), ou seja, B4 = R4 dada em (4.11). Para N = 8 temos 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  . Podemos observar pelo exemplo que B8 realiza a inversão de bits. Um vetor de entrada u8 1 ao passar por B8 será representado por ũ8 1 = (u1, u5, u3, u7, u2, u6, u4, u8). Uma implementação com N = 8 representando esta inversão de bits, pode ser observada na Figura 29. Ao se realizar uma análise detalhada dos nós do codificador mostrado na Figura 29, observa-se que as saídas x8 1 irão corresponder as seguintes entradas de ũ8 1 • x1→ ũ1, ũ2, ũ3, ũ4, ũ5, ũ6, ũ7, ũ8; • x2→ ũ2, ũ4, ũ6, ũ8; • x3→ ũ3, ũ4, ũ7, ũ8; 54 • x4→ ũ4, ũ8; • x5→ ũ5, ũ6, ũ7, ũ8; • x6→ ũ6, ũ8; • x7→ ũ7, ũ8; • x8→ ũ8. Figura 29 – Exemplo circuito da transformação F⊗3. x 3 x 4 x 1 x 2 ~ u = u u = u u = u u = u u = u u = u u = u u = u ~ ~ ~ ~ ~ ~ ~ x 7 x 8 x 5 x 6 3 7 1 5 4 8 2 6 3 4 1 2 7 8 5 6 Fonte: Próprio autor. Este formato do codificador mostra que para as entradas ũ8 1, as respectivas saídas serão x8 1 = ũ8 1F ⊗3, (4.35) onde F⊗3 é dada em (4.30). Exemplo 4.2.4 A partir dos cálculos do Exemplo 4.1.1 para a tomada de decisão da polarização de canal, considere um código polar (N, k,A, uAc) = (8, 4, {4, 6, 7, 8}, (0, 0, 0, 0)), ou seja, o código possui quatro entradas congeladas e quatro livres dadas por u4, u6, u7, u8 e os bits congelados são representados por 0. Vamos codificar a mensagem u = (0, 0, 0, 0, 0, 0, 1, 1) de duas formas. Inicialmente, utilizando a Equação 4.19, temos que 55 x8 1 = u8 1G8 = (0 0 0 0 0 0 1 1) ·  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  . = (0 0 0 0 1 1 1 1) Agora, após aplicar a inversão de bits do Exemplo 4.2.3 temos o vetor ũ8 1 = (00010001). Utilizando o circuito descrito na Figura 29 e a Equação 4.35 também podemos realizar a codificação. A Figura 30 mostra a codificação realizada. Figura 30 – Codificação u. - 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 W W W W W W W W Fonte: Próprio autor. 56 x8 1 = ũ8 1F ⊗3 = (0 0 0 1 0 0 0 1) ·  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  = (0 0 0 0 1 1 1 1), onde F⊗3 é dada em (4.30). 4.3 DECODIFICAÇÃO Como a codificação de códigos polares é bem definida e facilmente implementada utilizando o produto de Kronecker de matrizes, a busca por melhorias no desempenho dos códigos polares é realizada na sua decodificação. Dessa forma, a decodificação dos códigos polares é um tópico muito estudado e métodos de decodificação mais eficientes buscam ser desenvolvidos para melhorar o desempenho de tradução de uma mensagem de interesse. Nesta seção serão apresentados dois decodificadores, o decodificador por cancelamento sucessivo (Successive Cancellation Decoder - SC) e o decodificador por cancelamento sucessivo simplificado (Simplified Successive Cancellation Decoder - SSC). Em ambas as técnicas, o decodificador dispõe das informações sobre os valores e posições dos bits congelados, uAc e A, respectivamente. Além disso, ambas as técnicas de decodificação são do tipo de máxima verossimilhança, análoga à vista na Seção 3.2. Conforme é feita a decodificação do sinal, o vetor resultante ûN 1 é referente aos vetores uN 1 . A razão de verossimilhança (LikelihoodRatio - LR) é dada por L (i) N (yN 1 ,u i−1 1 ) = W i N(yN 1 ,u i−1 1 |ui = 0) W i N(yN 1 ,u i−1 1 |ui = 1) . (4.36) Considerando um decodificador de tamanhoN , a Equação 4.36 pode ser calculada a partir das seguintes relações recursivas f(a, b) = (ab) + 1 a+ b (4.37) e g(a, b, ûi−1) = a1−2·ûi−1b, (4.38) com a, b ∈ R. A decodificação do sinal, ou seja, o vetor resultante ûN 1 com os bits estimados, é dado 57 por ûi =  ui, se i /∈ Ac 0, se i ∈ Ac e L(i) N (yN 1 , û i−1 1 ) ≥ 1 1, se i ∈ Ace L(i) N (yN 1 , û i−1 1 ) < 1 . (4.39) 4.3.1 Decodificador por Cancelamento Sucessivo Proposto por Arikan, [ARIKAN 2009], o decodificador SC foi o primeiro decodificador desenvol- vido para ser utilizado em códigos polares. Este decodificador realiza as operações em todos os nós da arquiterura do código, ou seja, independente de saber os valores dos bits congelados este decodificador determina todos os nós para encontrar a mensagem de interesse. A Figura 31 representa a decodificação SC para um canal com N = 8. Neste caso, a decodificação apresenta três estágios, os quais são vistos da direita para a esquerda, e cada estágio disponibiliza as informações para o próximo estágio. Em cada nó de cada estágio é realizada uma operação com as fórmulas recursivas (4.37) e (4.38). Figura 31 – Exemplo arquitetura de decodificação SC com N = 8. L 1 L 1 L 1 L 1 L 1 L 1 L 1 L 1 L (1) 8 L 8 L 8 L 8 L 8 L 8 L 8 L 8 (2) (3) (4) (5) (6) (7) (8) f f f f f f f g g g g g g g g g g g (1) (2) (3) (4) (5) (6) (7) (8) 1 2 3 4 3 4 4 2 1 2 5 6 û 2 û û û û û 5 3 7 6 4 û û û û û û û û û û û û f f f f fg û 1 Fonte: Próprio autor. No Exemplo 4.3.1 será realizado o passo a passo da decodificação. Exemplo 4.3.1 Considere um código de tamanho N = 8 com taxa 1/2, transmitido por um canal AWGN com Eb/N0 = 1 dB. Baseando-se no Exemplo 4.1.1 as entradas (u1, u2, u3, u5) serão congela- das e serão transmitidos bits 0’s. Supondo que na saída deste canal com ruído AWGN, foi recebido o seguinte vetor y = (-1.1241, 2.4896, 0.4090, 2.4171, 1.6714, -2.2074, 1.7172, 0.6302). 58 Aplicando as Equações (4.37) e (4.38), juntamente da relação (4.39), iremos realizar a decodificação deste vetor por cancelamento sucessivo. Os valores encontrados em cada etapa da decodificação são apresentados na Figura 32 e seus cálculos explicados a seguir. Inicialmente, como a decodificação começa da direita para a esquerda, os valores recebidos são utilizados para calcular todos os valores de f como segue • Para L(1) 2 −→ f(a, b), a = L (1) 1 e b = L (2) 1 , temos f(−1.1241, 2.4896) = −1.1241 · (2.4896) + 1 −1.1241 + (2.4896) = −1.3172. • Para L(3) 2 −→ f(a, b), a = L (3) 1 e b = L (4) 1 , temos f(0.4090, 2.4171) = 0.4090 · (2.4171) + 1 0.4090 + (2.4171) = 0.7036. • Para L(5) 2 −→ f(a, b), a = L (5) 1 e b = L (6) 1 , temos f(1.6714,−2.2074) = 1.6714 · (−2.2074) + 1 1.6714 + (−2.2074) = 5.0183. • Para L(7) 2 −→ f(a, b), a = L (7) 1 e b = L (8) 1 , temos f(1.7172, 0.6302) = 1.7172 · (0.6302) + 1 1.7172 + (0.6302) = 0.8870. Após realizar todos esses cálculos, o decodificador avança de estágio apenas com esses valores definidos e realiza os seguintes cálculos • Para L(1) 4 −→ f(a, b), a = L (1) 2 e b = L (3) 2 , temos f(−1.3172, 0.7036) = −1.3172 · (0.7036) + 1 −1.3172 + (0.7036) = −0.1191. • Para L(5) 4 −→ f(a, b), a = L (5) 2 e b = L (7) 2 , temos f(5.0183, 0.8870) = 5.0183 · (0.8870) + 1 5.0183 + (0.8870) = 0.9231. Logo após, o decodificador avança mais uma vez de estágio e realiza os seguintes cálculos • Para L(1) 8 −→ f(a, b), a = L (1) 4 e b = L (5) 4 , temos f(−0.1191, 0.9231) = −0.1191 · (0.9231) + 1 −0.1191 + (0.9231) = 1.1070. 59 Figura 32 – Exemplo decodificação SC com N = 8. f f f f f f f f f f f f g g g g g g g g g g g g 1 2 3 4 5 6 7 8 û û û û û û û û = 0 = 1 = 0 = 0 = 1 = 1 = 0 = 0 -1.1241 -2.4896 0.4090 2.4171 1.6714 -2.2074 1.7172 0.6302 1.1070 -0.1099 -0.8869 -4.1261 1.7679 -0.5411 -0.7261 0.3070 -0.1191 0.9231 -0.9269 4.4514 -0.5403 -13.0881 -3.2717 -0.4847 -1.3172 5.0183 0.7036 0.8870 -1.3207 5.9095 -2.2147 0.3670 Fonte: Próprio autor. Nesse momento, o decodificador verifica primeiramente se o vetor recebido é um bit congelado ou um bit de informação. Dessa forma, como o exemplo considera que o vetor u1 é um bit congelado, então û1 = 0. Seguindo, o decodificador calcula a segunda posição do vetor pela função g, que depende apenas da primeira posição do vetor • Para L(5) 8 −→ g(a, b, ûi−1), a = L (1) 4 , b = L (5) 4 e ûi−1 = 1, temos g(−0.1191, 0.9231, 0) = −0.11911−2·0 · 0.9231 = −0.1099. Como consideramos o vetor u2 também um bit congelado, então û2 = 0. Neste momento o decodifica- dor tem os valores de û1 e û2, ele os utiliza para calcular a terceira posição do vetor. • Para L(3) 4 −→ g(a, b, ûi−1), a = L (1) 2 , b = L (3) 2 e ûi−1 = 1, temos g(−1.3172, 0.7036, 0) = −1.31721−2·0 · 0.7036 = −0.9269. • Para L(7) 4 −→ g(a, b, ûi−1), a = L (5) 2 , b = L (7) 2 e ûi−1 = 0, temos g(5.0183, 0.8870, 0) = 5.01831−2·0 · 0.8870 = 4.4514. • Para L(3) 8 −→ f(a, b), a = L (3) 4 e b = L (7) 4 , temos f(−0.9269, 4.4514) = −0.9269 · (4.4514) + 1 −0.9269 + (4.4514) = −0.8869. 60 Como o vetor u3 é um bit congelado, û3 = 0. Seguindo, para calcular a quarta posição do vetor • Para L(7) 8 −→ g(a, b, ûi−1), a = L (3) 4 , b = L (7) 4 e ûi−1 = 0, temos g(−0.9269, 4.4514, 0) = −0.92691−2·0 · 4.4514 = −4.1261. Por (4.39), concluímos que û4 = 1. Assim, como o decodificador identificou os quatro primeiros valores do vetor enviado, ele os utiliza para calcular a parte restante do primeiro estágio. Sendo assim, temos • Para L(2) 2 −→ g(a, b, ûi−1), a = L (1) 1 , b = L (2) 1 e ûi−1 = 1, temos g(−1.1241, 2.4896, 1) = −1.12411−2·1 · (2.4896) = −2.2147. • Para L(4) 2 −→ g(a, b, ûi−1), a = L (3) 1 , b = L (4) 1 e ûi−1 = 0, temos g(0.4090, 2.4171, 1) = 0.40901−2·1 · (2.4171) = 5.9095. • Para L(6) 2 −→ g(a, b, ûi−1), a = L (5) 1 , b = L (6) 1 e ûi−1 = 0, temos g(1.6714,−2.2074, 0) = 1.67141−2·0 · (−2.2074) = −1.3207. • Para L(8) 2 −→ g(a, b, ûi−1), a = L (7) 1 , b = L (8) 1 e ûi−1 = 0, temos g(1.7172, 0.6302, 0) = 1.71721−2·1 · (0.6302) = 0.3670. Passando para o próximo estágio • Para L(2) 4 −→ f(a, b), a = L (2) 2 e b = L (4) 2 , temos f(−2.2147, 5.9095) = (−2.2147) · (5.9095) + 1 (−2.2147) + (5.9095) = −3.2717. • Para L(6) 4 −→ f(a, b), a = L (6) 2 e b = L (8) 2 , temos f(−1.3207, 0.3670) = (−1.3207) · (0.3670) + 1 (−1.3207) + (0.3670) = −0.5403. • Para L(2) 8 −→ f(a, b), a = L (2) 4 e b = L (6) 4 , temos f(−3.2717,−0.5403) = (−3.2717) · (−0.5403) + 1 (−3.2717) + (−0.5403) = −0.8809. Como o vetor u5 é um bit congelado, então û5 = 0. Assim, para calcular a sexta posição do vetor 61 • Para L(6) 8 −→ g(a, b, ûi−1), a = L (2) 4 , b = L (6) 4 e ûi−1 = 1, temos g(−3.2717,−0.5403, 0) = (−3.2717)1−2·0 · (−0.5403) = 1.7679. Por (4.39), temos que û6 = 0. Para calcular û7, temos • Para L(4) 4 −→ g(a, b, ûi−1), a = L (2) 2 , b = L (4) 2 e ûi−1 = 1, temos g(−2.2147, 5.9095, 0) = (−2.2147)1−2·0 · (5.9095) = −13.0881. • Para L(8) 4 −→ g(a, b, ûi−1), a = L (6) 2 , b = L (8) 2 e ûi−1 = 0, temos g(−1.3207, 0.3670, 0) = (−1.3207)1−2·0 · (0.3670) = −0.4847. • Para L(4) 8 −→ f(a, b), a = L (4) 4 e b = L (8) 4 , temos f(−13.0881,−0.4847) = −13.0881 · −0.4847 + 1 −13.0881 +−0.4847 = −0.5411. Pela relação (4.39), concluímos que û7 = 1. Por fim, • Para L(8) 8 −→ g(a, b, ûi−1), a = L (4) 4 , b = L (8) 4 e ûi−1 = 0, temos g(−13.0881,−0.4847, 0) = −13.08811−2·0 · −0.4847 = 0.0370. Novamente pela relação (4.39), temos que û8 = 1. Portanto, o vetor decodificado é û = (0, 0, 0, 1, 0, 0, 1, 1). Podemos observar pelo exemplo que todos os nós do código foram determinados mesmo que o decodificador já tenha o valor do bit congelado, deste modo, pode-se dizer que este decodificador tem uma perda de processamento, afinal, aloca recursos para operações desnecessárias. Uma análise importante do decodificador é determinar a quantidade de ciclos de clocks que o processador precisa para decodificar uma mensagem de interesse. Entende-se por clock, ou ciclo de clock, como sendo o número de ações que o processador consegue executar por segundo, como inicializar um programa, escrever algo na memória ou realizar alguns cálculos. Na Figura 33 podemos observar uma representação da quantidade de clocks que o processador necessita para decodificar a mensagem do Exemplo 4.3.1. Cada clock do processador calcula o máximo de nós possíveis com a informação que tem no momento. No primeiro clock temos o cálculo de 4 nós f , já no segundo, 2 nós f , no terceiro um nó f , determinando assim o primeiro bit de informação e assim por diante. Observa-se que são necessários 14 ciclos de clock para decodificar a mensagem completa. 62 Figura 33 – Ciclo de clock do processador nos decodificador SC. f f f f f f f f f f f f g g g g g g g g g g g g 1 2 3 4 5 6 7 8 û û û û û û û û = 0 = 1 = 0 = 0 = 1 = 1 = 0 = 0 -1.1241 -2.4896 0.4090 2.4171 1.6714 -2.2074 1.7172 0.6302 1 1 1 1 2 23 4 5 5 8 8 6 7 8 8 9 9 10 11 12 12 13 14 Fonte: Próprio autor. A decodificação deste código pode ser representada a partir de um gráfico de árvore, nesta representação cada bit estimado ûi é representado por um nó. Temos dois tipos de nós N0 que corresponde aos bits congelados e N1 que corrensponde aos bits de informação. A origem de dois nós N0 é também um nó N0 e possui taxa de informação igual a zero. A combinação de dois nós N1 correspodem a um nó origem também N1, que possui taxa de informação igual a 1. Já um nó origem de dois nós de diferentes tipos é um nó NR e possui taxa 0 < R < 1. Na Figura 34 temos a representação de um código polar (N, k) = (8, 4). Os circulos brancos são nós N0, os circulos pretos representam os nós N1, os circulos cinza representam os nós NR e dv é a profundidade de v no código. Figura 34 – Arquiterura em árvore SC com N = 8 e R = 1/2. d = 0 v d = 1 v d = 2 v d = 3 v Fonte: Próprio autor. Cada um dos circulos representa um clock que o processador terá que dar para fazer os cálculos referente a este nó. Em decodificadores SC, todos os nós são calculados, então podemos dizer que a quantidade de clocks que um decodificador utiliza para decodificar uma mensagem é dada 63 por, [LEROUX et al. 2011, ZHANG e PARHI 2014], clockSC = 2(N − 1). (4.40) Uma outra medida importante de um código é o throughput, ou seja, a taxa de processamento de informação. Este parâmetro mede a quantidade de bits que são decodificados por segundo levando em consideração um ciclo de clock do processador. O throughput de um decodificador SC é dado pela seguinte equação T = k clockSC ∗ tp , (4.41) onde T é dado em bits/s e tp é o tempo necessário para que o processador codifique e decodifique uma mensagem de interesse, [LEROUX et al. 2011, SARKIS e GROSS 2013a]. 4.3.2 Decodificador por Cancelamento Sucessivo Simplificado Este decodificador é uma melhoria do decodificador SC, pois sabendo a informação dos valores dos bits congelados, os nós que seriam necessários para determinar estes bits não são calculados. Deste modo, tem-se um ganho de processamento, pois recursos não são gastos desnecessariamente e há melhoria de latência, pois a mensagem de interesse é decodificada mais rapidamente. A Figura 35 representa um canal N = 8, podemos observar que este decodificador também apresenta três estágios, entretanto, o cálculo de alguns nós não são necessários para determinar os bits congelados. No Exemplo 4.3.2 será realizado o passo a passo da decodificação. Figura 35 – Exemplo arquitetura de decodificação SSC com N = 8. 1 1 1 1 1 1 1 1 (1) (2) (3) (4) (5) (6) (7) (8) 1 2 3 4 3 4 4 2 1 2 5 6 û 2 û û û û û 5 3 7 6 4 û û û û û û û û û û û û L (1) 8 L 8 L 8 L 8 L 8 L 8 L 8 L 8 (2) (3) (4) (5) (6) (7) (8) f g g g f f g g g g f f f f g g g g L L L L L L L L Fonte: Próprio autor. 64 Exemplo 4.3.2 Considere um código de tamanho N = 8 com taxa 1/2, transmitido por um canal AWGN com Eb/N0 = 1 dB. Baseando-se no Exemplo 4.1.1 as entradas (u1, u2, u3, u5) serão congela- das e serão transmitidos bits 0’s. Supondo que na saída deste canal com ruído AWGN, foi recebido o seguinte vetor y = (-0.7946, 1.8403, 0.1119, 1.1000, -1.5445, -0.6964, -1.6003, -0.5100). Aplicando as Equações (4.37) e (4.38), juntamente da relação (4.39), e sabendo que (u1 = 0, u2 = 0, u3 = 0, u5 = 0) iremos realizar a decodificação deste vetor por cancelamento sucessivo simplificado. Os valores encontrados em cada etapa da decodificação são apresentados na Figura 36 e explicados a seguir. Inicialmente, como a decodificação começa da direita para a esquerda, os valores recebidos são utilizados para calcular todos os valores de f como segue Figura 36 – Exemplo decodificação SSC com N = 8. f f f f f f f g g g g g g g g g g g 1 2 3 4 5 6 7 8 û û û û û û û û = 0 = 1 = 0 = 1 = 1 = 1 = 0 = 0 -0.7946 1.8403 0.1119 1.1000 -1.5445 -0.6964 -1.6003 -0.5100 -0.3267 -4.3049 -0.5411 -0.1665 -0.4098 0.7971 1.4860 -4.2424 -2.8969 0.7067 -0.4422 -0.9262 0.9266 -0.8606 0.4509 9.8250 -2.3158 0.3187 Fonte: Próprio autor. • Para L(1) 2 −→ f(a, b), a = L (1) 1 e b = L (2) 1 , temos f(−0.7946, 1.8403) = −0.7946 · (1.8403) + 1 −0.7946 + (1.8403) = −0.4422. • Para L(3) 2 −→ f(a, b), a = L (3) 1 e b = L (4) 1 , temos f(0.1119, 1.1000) = 0.1119 · (1.1000) + 1 0.1119 + (1.1000) = 0.9266. • Para L(5) 2 −→ f(a, b), a = L (5) 1 e b = L (6) 1 , temos f(−1.5445,−0.6964) = −1.5445 · (−0.6964) + 1 −1.5445 + (−0.6964) = −0.9262. 65 • Para L(7) 2 −→ f(a, b), a = L (7) 1 e b = L (8) 1 , temos f(−1.6003,−0.5100) = −1.6003 · (−0.5100) + 1 −1.6003 + (−0.5100) = −0.8606. Após realizar todos esses cálculos, o decodificador avança de estágio com esses valores definidos e realiza os seguintes cálculos • Para L(3) 4 −→ g(a, b, ûi−1), a = L (1) 2 , b = L (3) 2 e ûi−1 = 1, temos g(−0.4422, 0.9266, 0) = −0.44221−2·0 · 0.9266 = 0.4098. • Para L(7) 4 −→ g(a, b, ûi−1), a = L (5) 2 , b = L (7) 2 e ûi−1 = 0, temos g(−0.9262,−0.8606, 0) = −0.92621−2·0 · −0.8606 = 0.7971. • Para L(7) 8 −→ g(a, b, ûi−1), a = L (3) 4 , b = L (7) 4 e ûi−1 = 0, temos g(0.4098, 0.7971, 0) = 0.40981−2·0 · 0.7971 = −0.3267. A partir de (4.39), temos que û4 = 1. Assim, como o decodificador sabe os quatro primeiros valores do vetor enviado, ele os utiliza para calcular a parte restante do primeiro estágio. Sendo assim, temos • Para L(2) 2 −→ g(a, b, ûi−1), a = L (1) 1 , b = L (2) 1 e ûi−1 = 1, temos g(−0.7946, 1.8403, 1) = −0.79461−2·1 · (1.8403) = −2.3158. • Para L(4) 2 −→ g(a, b, ûi−1), a = L (3) 1 , b = L (4) 1 e ûi−1 = 0, temos g(0.1119, 1.1000, 1) = 0.11191−2·1 · (1.1000) = 9.8250. • Para L(6) 2 −→ g(a, b, ûi−1), a = L (5) 1 , b = L (6) 1 e ûi−1 = 0, temos g(−1.5445,−0.6964, 1) = −1.54451−2·1 · (−0.6964) = 0.4509. • Para L(8) 2 −→ g(a, b, ûi−1), a = L (7) 1 , b = L (8) 1 e ûi−1 = 0, temos g(−1.6003,−0.5100, 0) = −1.60031−2·1 · (−0.5100) = 0.3187. Passando para o próximo estágio • Para L(2) 4 −→ f(a, b), a = L (2) 2 e b = L (4) 2 , temos f(−2.3158, 9.8250) = (−2.3158) · (9.8250) + 1 (−2.3158) + (9.8250) = −2.8969. 66 • Para L(6) 4 −→ f(a, b), a = L (6) 2 e b = L (8) 2 , temos f(0.4509, 0.3187) = (0.4509) · (0.3187) + 1 (0.4509) + (0.3187) = 1.4860. • Para L(6) 8 −→ g(a, b, ûi−1), a = L (2) 4 , b = L (6) 4 e ûi−1 = 1, temos g(−2.8969, 1.4860, 0) = (−2.8969)1−2·0 · (1.4860) = −4.3049. Por (4.39), segue que û6 = 1. Para calcular û7, temos • Para L(4) 4 −→ g(a, b, ûi−1), a = L (2) 2 , b = L (4) 2 e ûi−1 = 1, temos g(−2.3158, 9.8250, 1) = (−2.3158)1−2·1 · (9.8250) = −4.2424. • Para L(8) 4 −→ g(a, b, ûi−1), a = L (6) 2 , b = L (8) 2 e ûi−1 = 0, temos g(0.4509, 0.3187, 1) = (0.4509)1−2·1 · (0.3187) = 0.7067. • Para L(4) 8 −→ f(a, b), a = L (4) 4 e b = L (8) 4 , temos f(−4.2424, 0.7067) = −4.2424 · 0.7067 + 1 −4.2424 + 0.7067 = 0.5652. Pela relação (4.39), temos que û7 = 1. • Para L(8) 8 −→ g(a, b, ûi−1), a = L (4) 4 , b = L (8) 4 e ûi−1 = 0, temos g(−4.2424, 0.7067, 1) = −4.24241−2·1 · 0.7067 = −0.1665. Novamente pela relação (4.39), concluímos que û8 = 1. Portanto, o vetor original é û = (0, 0, 0, 1, 0, 1, 1, 1). Podemos observar pelo exemplo que nem todos os nós do código foram determinados, pois o decodificador já possui a informação dos bits congelados. Na Figura 37 podemos observar uma imagem representando a quantidade de clocks que um processador necessita para decodificar a mensagem do Exemplo 4.3.2. No primeiro clock temos o cálculo de 4 nós f , já no segundo, 2 nós g, no terceiro um nó g, determinando assim o primeiro bit de informação e assim por diante. Observa-se que são necessários 9 ciclos de clock para decodificar a mensagem completa. Logo, decodificadores SSC utilizam menos clocks do processador para decodificar uma mesma mensagem, visto que não necessitam calcular os nós N0. 67 Figura 37 – Ciclo de clock do processador no decodificador SSC. f f f f f f f g g g g g g g g g g g 1 2 3 4 5 6 7 8 û û û û û û û û = 0 = 1 = 0 = 1 = 1 = 1 = 0 = 0 -0.7946 1.8403 0.1119 1.1000 -1.5445 -0.6964 -1.6003 -0.5100 1 1 1 1 2 2 4 4 3 4 4 5 56 7 7 8 9 Fonte: Próprio autor. Na Figura 38 podemos observar a representação de arvores de decodificadores SSC com diferentes taxas. Figura 38 – Decodificadores em árvore SSC para diferentes taxas. R = 1/2 R = 5/8R = 3/8 d = 0 v d = 1 v d = 2 v d = 3 v Fonte: Próprio autor. A quantidade de ciclos de clock necessários para decodificar um decodificador SSC é dada pela seguinte equação clockSSC = 2(N − 1)− ∑ i (2di+1 − 1)− ∑ j [(2dj+1 − 1)− (dj + 1)], (4.42) onde i e j, representam a quantidade de sub árvores formadas por nós N0 e N1, respectivamente, que estão contidas na árvore de decodificação, [ZHANG e PARHI 2014]. Vale ressaltar que esta equação conta o primeiro clock como sendo o clock 0, assim, vamos somar 1 clock na Equação 4.42 para contabilizar este clock, de modo clockSSC = 1 + 2(N − 1)− ∑ i (2di+1 − 1)− ∑ j [(2dj+1 − 1)− (dj + 1)]. (4.43) 68 Exemplo 4.3.3 Considerando a Figura 38 vamos realizar a contagem de clocks para diferentes taxas de codificação. • Para R = 3/8, temos duas sub-árvores de N0, uma com di = 2 e outra com di = 0, duas N1, uma com di = 1 e outra com di = 0. Assim, clockSSC = 1 + 14− (7 + 1)− [(3 + 1)− (2 + 1)] = 6. • Para R = 1/2, temos três sub-árvores deN0, uma com di = 1 e duas com di = 0. ParaN1 temos uma com di = 1 e duas com di = 0. Assim, clockSSC = 1 + 14− (3 + 1 + 1)− [(3 + 1 + 1)− (2 + 1 + 1)] = 9. • Para R = 5/8, temos duas sub-árvores de N0, uma com di = 1 e outra com di = 0. Para N1 temos duas com di = 1 e uma com di = 0. Assim, clockSSC = 1 + 14− (3 + 1)− [(3 + 3 + 1)− (2 + 2 + 1)] = 9. Utilizando (4.41) e (4.42), o throughput de um decodificador SSC será T = k clockSSC ∗ tp . (4.44) No Capítulo 5 será realizada uma implementação computacional dos códigos polares que tem como objetivo comparar o desempenho deste código com os códigos convolucionais para correção e detecção de erros, assim como a latência e o throughput. 69 5 IMPLEMENTAÇÃO, ANÁLISES E RESULTADOS Neste capítulo, apresentaremos as simulações realizadas e os resultados obtidos de uma implemen- tação computacional no software MATLAB. Inicialmente, será realizada a implementação dos códigos convolucionais e polares, para avaliação da taxa de erro de bit (Bit Error Rate - BER), para posterior- mente, comparar o desempenho destes códigos em cenários URC (Ultra Reliability Communications), com transmissão de pacotes curtos, analisando a latência e o throughput como previsto nos sistemas 5G. A abordagem de Monte Carlo foi utilizada na implementação, a mesma baseia-se na Lei dos Grandes Números, que afirma que ao realizar um mesmo experimento um elevado número de vezes a média da estatística de interesse converge para o parâmetro, ou seja, a probabilidade do evento de interesse ocorrer é dado pela frequência relativa, [JACOBINI e LUGLI 2012]. As simulações de Monte Carlo são definidas como um método estatístico que se baseia na sucessiva simulação de várias realizações de um mesmo experimento aleatório a fim de obter um resultado numérico aproximado, ou seja, repete-se uma mesma simulação aleatória um elevado número de vezes para encontrar uma estimativa do parâmetro de interesse a partir da estatística correspondente calculada da distribuição amostral. A estimativa de um evento de interesse (A) utilizando o método de Monte Carlo é dada da seguinte forma Pr(A) = lim N ′→∞ N ′A N ′ , (5.1) onde N ′ é a quantidade de simulações realizadas e N ′A o número de ocorrências de um determinado evento de interesse A. Sabendo que a estimativa leva em consideração a Lei dos Grandes Números, resultados precisos podem ser tomados ao simular o experimento um elevado número de vezes e fazendo N ′ tender ao infinito, o resultado torna-se preciso. Para as simulações realizadas, a fim de obter um resultado representativo estatisticamente cada ponto na curva tem 105 realizações. O simulador implementado gera k bits aleatórios, que passam pelos codificadores (convolucional e polar), ambos com taxa R = k/N = 1/2. Após uma mensagem u ser codificada em c, ela é inserida em um modulador BPSK (Binary Phase Shift Keying), que foi escolhido pois os bits serão transmitidos um a um e este modulador pode ser usado de forma simples para esta aplicação, posteriormente a mensagem é transmitida por um canal que irá inserir ruído AWGN. Uma mensagem r é recebida, demodulada e decodificada em uma mensagem û. Para a simulação da BER, a mensagem û que foi decodificada será comparada com a palavra-código u transmitida, para contabilizar, caso sejam diferentes, a ocorrência de erros de decodificação. Para a implementação dos códigos convolucionais, utilizamos o código convolucional (2, 1, 7) que possui máquina de estados apresentada na Figura 9. O codificador utilizado foi baseado no diagrama de treliça e o decodificador no algortimo de Viterbi. A transmissão de mensagens para diferentes comprimentos de palavras foram realizadas, com taxa de transmissão fixa R = 1/2 e os valores de Eb/N0 foram variados de -2 a 5 dB, com a densidade de potência do ruído fixo N0 = 2. Na Figura 39 encontram-se os resultados obtidos. 70 Figura 39 – Simulação da BER para códigos convolucionais com (N,k) = (64,32; 128,64; 256,128; 512,256; 1024,512; 2048,1024) Eb/N0 em dB -2 -1 0 1 2 3 4 5 B it E rr o r R a te - B E R 10 -3 10 -2 10 -1 10 0 Convolucional - R = 1/2 N = 64 N = 128 N = 256 N = 512 N = 1024 N = 2048 Fonte: Próprio autor. Pode-se observar que as curvas geradas não possuem grande alteração com a variação do com- primento da palavra código transmitida, entretanto, caso a potência de transmissão seja maior, o desempenho do código em correção e detecção de erro aumenta. Existe um ponto interessante nas curvas obtidas, q