ads:
Franklin Antonio Sanchez Paiba
C´odigos Fontanais Bidimensionais para Canais
com Apagamento
Disserta¸c˜ao de Mestrado
Disserta¸c˜ao apresentada como requisito parcial para obten¸c˜ao do
grau de Mestre pelo Programa de P´os–gradua¸c˜ao em Engenharia
El´etrica do Departamento de Engenharia El´etrica da PUC–Rio
Orientador: Prof. Weiler Alves Finamore
Rio de Janeiro
Julho de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Franklin Antonio Sanchez Paiba
C´odigos Fontanais Bidimensionais para Canais
com Apagamento
Disserta¸c˜ao apresentada como requisito parcial para obten¸c˜ao do
grau de Mestre pelo Programa de P´os–gradua¸c˜ao em Engenha-
ria El´etrica do Departamento de Engenharia El´etrica do Centro
T´ecnico Cient´ıfico da PUC–Rio. Aprovada pela Comiss˜ao Exami-
nadora abaixo assinada.
Prof. Weiler Alves Finamore
Orientador
Departamento de Engenharia El´etrica — PUC–Rio
Prof. Raimundo Sampaio Neto
Departamento de Engenharia El´etrica — PUC–Rio
Prof. Marco Antonio Grivet Matoso Maia
Departamento de Engenharia El´etrica — PUC–Rio
Prof. Valdemar Cardoso Da Rocha J´unior
Departamento de Engenharia El´etrica — UFPE
Prof. Jos´e Eugenio Leal
Coordenador Setorial do Centro T´ecnico Cient´ıfico — PUC–Rio
Rio de Janeiro, 03 de Julho de 2008
ads:
Todos os direitos reservados.
´
E proibida a reprodu¸c˜ao total
ou parcial do trabalho sem autoriza¸c˜ao da universidade, do
autor e do orientador.
Franklin Antonio Sanchez Paiba
Graduou–se em Engenharia Electr´onica na Pontif´ıcia Univer-
sidade Cat´olica del Per´u (Lima, Per´u).
Ficha Catalogr´afica
Sanchez Paiba, Franklin Antonio
C´odigos Fontanais Bidimensionais para Canais com Apa-
gamento / Franklin Antonio Sanchez Paiba; orientador: Weiler
Alves Finamore. — Rio de Janeiro : PUC–Rio, Departamento
de Engenharia El´etrica, 2008.
v., 81 f: il. ; 29,7 cm
1. Disserta¸c˜ao (mestrado) - Pontif´ıcia Universidade
Cat´olica do Rio de Janeiro, Departamento de Engenharia
El´etrica.
Inclui referˆencias bibliogr´aficas.
1. Engenharia El´etrica – Tese. 2. C´odigos Fontanais. 3.
C´odigos LT. 4. C´odigos Raptor. 5. C´odigos com taxa vers´atil.
6. Canais com apagamento. 7. Distribui¸c˜ao de graus. I. Alves
Finamore, Weiler. II. Pontif´ıcia Universidade Cat´olica do Rio
de Janeiro. Departamento de Engenharia El´etrica. III. T´ıtulo.
CDD: 621.3
Agradecimentos
A meu orientador Weiler Finamore pela amizade, paciˆencia, com-
preens˜ao, confian¸ca e excelente orienta¸c˜ao, que me motivaram para a reali-
za¸c˜ao do presente trabalho.
`
A CAPES e `a PUC–Rio, pelos aux´ılios concedidos, sem os quais este
trabalho n˜ao poderia ter sido realizado.
Aos professores do CETUC, em especial aos professores Jos´e Mauro e
Raimundo, que agregaram conhecimento valioso em minha vida professional.
Aos meus pais, Giner e Yolanda, pela educa¸c˜ao, aten¸c˜ao e carinho de
todas as horas.
Aos meus irma˜os Karin e Ivan, pelo carinho, apoio, incentivo e por estar
sempre presentes em minha vida.
A minha amiga Kelly, pela aten¸c˜ao, carinho e apoio incondicional em
todo momento.
A meu amigo Humberto, pela ajuda, paciˆencia e orienta¸c˜ao.
Ao meus primos Gerardo, Sara e Jose Luis por todo apoio, paciˆencia e
compreens˜ao.
Ao pessoal do CETUC, em particular ao Dick, Carlos, Marcelo e Tiago,
pelo companheirismo e apoio em muitas ocasi˜oes.
A todos os amigos e familiares que de uma forma ou de outra me
estimularam ou me ajudaram.
Resumo
Sanchez Paiba, Franklin Antonio; Alves Finamore, Weiler. C´odigos
Fontanais Bidimensionais para Canais com Apagamento.
Rio de Janeiro, 2008. 81p. Disserta¸c˜ao de Mestrado — Departa-
mento de Engenharia El´etrica, Pontif´ıcia Universidade Cat´olica do
Rio de Janeiro.
Esta disserta¸c˜ao aborda o estudo de c´odigos fontanais (c´odigos LT e c´odigos
Raptor) que s˜ao uma classe de c´odigos criados para a transmiss˜ao de
dados de maneira confi´avel e eficiente atrav´es de canais os quais podem
ser modelados como canais com apagamento. Os c´odigos LT e c´odigos
Raptor s˜ao denominados c´odigos fontanais, devido a que eles s˜ao uma
boa aproxima¸c˜ao para o conceito de fontanas digitais. Al´em disso, eles s˜ao
classificados como c´odigos de taxa vers´atil, no sentido que o n´umero de
s´ımbolos codificados que podem ser gerados a partir dos dados de entrada
´e potencialmente ilimitado.
C´odigos LT s˜ao capazes de recuperar, com probabilidade maior do que
(1 − δ), um conjunto de k s´ımbolos de entrada a partir de quaisquer
k + O(
√
k ln
2
(k/δ)) s´ımbolos codificados recebidos, com uma m´edia de
O(k ln(k/δ)) opera¸c˜oes XOR. Os c´odigos Raptor s˜ao uma extens˜ao de
c´odigos LT, na qual o processo de codifica¸c˜ao ´e composto de duas etapas:
um c´odigo de bloco de comprimento fixo (denominado pr´e-c´odigo) e um
c´odigo LT com uma distribui¸c˜ao de graus apropriada.
Investigou-se o desempenho dos c´odigos LT usando duas novas distribui¸c˜oes
de graus (S´oliton Robusta Melhorada e S´oliton Robusta Truncada) e foi
proposto um modelo de c´odigos LT Bidimensionais, na qual os s´ımbolos
de entrada s˜ao agrupados em forma de matriz. Neste esquema os blocos
correspondentes `as linhas da matriz s˜ao codificados usando um c´odigo LT
e, em seguida, a matriz resultante tem suas colunas tamb´em codificadas
usando um c´odigo LT. Ainda que a complexidade do esquema tenha sido
dobrada o desempenho alcan¸cado pelos c´odigos LT Bidimensionais superou
o desempenho dos c´odigos LT convencionais para situa¸c˜oes em que a
qualidade do canal BEC ´e elevada.
Palavras–chave
C´odigos Fontanais. C´odigos LT. C´odigos Raptor. C´odigos com taxa
vers´atil. Canais com apagamento. Distribui¸c˜ao de graus.
Abstract
Sanchez Paiba, Franklin Antonio; Alves Finamore, Weiler. Bidi-
mensional Fountain Codes for Erasure Channels. Rio de Ja-
neiro, 2008. 81p. MsC Dissertation — Departamento de Engenharia
El´etrica, Pontif´ıcia Universidade Cat´olica do Rio de Janeiro.
Fountain Codes (LT Codes and Raptor Codes) are a class of codes proposed
to efficient and reliably transmit data through Erasure Channels. LT Codes
and Raptor Codes are a good approximation to the concept of digital
fountain and as such are named as fountain codes. They are said to be
rateless codes in the sense that the number of symbols produced by the
encoder could grow, potentially, to infinite.
With probability of success larger than (1−δ), a decoder of an LT code based
scheme can recover the k transmitted symbols from any received block of
k + O(
√
k ln
2
(k/δ)) correct symbols with an average of O(k ln(k/δ)) XOR
operations. Raptor codes are an extension of the LT codes idea, with a
tandem scheme where a fixed length block code (namely a pre-code) is
followed by an LT code that uses a properly chosen degree distribution.
In this dissertation the performance of LT codes with two recently propo-
sed degree distributions, the Improved Robust Soliton and the Truncated
Soliton Robust Distribution were investigated. A new scheme called Bidi-
mensional LT Codes, has been proposed. In this scheme the input symbols
are structured in a matrix form and afterwards the blocks corresponding
to the lines of the matrix are encoded with an LT code. The columns of
the new matrix so obtained are next encoded with a similar LT code. The
complexity of the new scheme is doubled and yet its performance only just
surpasses that of the conventional LT scheme for high quality BEC.
Keywords
Fountain Codes. LT Codes. Raptor Codes. Rateless Codes. Era-
sure Channels. Degree Distribution.
Sum´ario
Sum´ario das nota¸c˜oes 12
1 Introdu¸c˜ao 13
1.1 Motiva¸c˜ao 13
1.2 Sistema de Comunica¸c˜ao 14
1.3 Modelo de canais com apagamentos 15
1.4 Fontanas Digitais 16
1.5 Objetivos e organiza¸c˜ao do trabalho 18
2 C´odigos LT 20
2.1 Codifica¸c˜ao 21
2.2 Codificador LT como um c´odigo em grafo 23
2.3 Decodifica¸c˜ao 25
2.3.1 O processo LT 27
2.4 Distribui¸c˜oes de graus 30
2.4.1 Distribui¸c˜ao S´oliton Ideal 30
2.4.2 Distribui¸c˜ao S´oliton Robusta 30
2.5 M´etodo das Transforma¸c˜oes Inversas 33
2.5.1 Determina¸c˜ao do grau do s´ımbolo codificado 33
2.6 Escolha dos parˆametros da distribui¸c˜ao S´oliton Robusta 34
2.6.1 Resultados obtidos das simula¸c˜oes 34
2.7 An´alise de desempenho 37
2.7.1 Desempenho em canais ideais 37
2.7.2 Desempenho em canais com apagamento 39
2.8 Compara¸c˜ao com c´odigos tradicionais para canais com apagamento 40
2.8.1 C´odigos Reed-Solomon 41
2.8.2 C´odigos Tornado 41
3 Projetando a distribui¸c˜ao de graus para c´odigos LT 43
3.1 Distribui¸c˜ao S´oliton Ideal 44
3.2 Distribui¸c˜ao S´oliton Robusta 46
3.2.1 An´alise da distribui¸c˜ao S´oliton Robusta 49
4 C´odigos LT Bidimensionais 52
4.1 Distribui¸c˜ao de graus S´oliton Robusta Melhorada 52
4.2 Distribui¸c˜ao S´oliton Robusta Truncada para C´odigos LT Sistem´aticos 55
4.3 Esquema de c´odigos LT bidimensionais 57
4.3.1 Codifica¸c˜ao bidimensional 58
4.3.2 Decodifica¸c˜ao bidimensional 58
4.3.3 Configura¸c˜oes Utilizadas 59
4.4 Resultados obtidos 59
5 Conclus˜oes e Sugest˜oes para trabalhos futuros 64
5.1 Conclus˜oes 64
5.2 Sugest˜oes para trabalhos futuros 65
Referˆencias Bibliogr´aficas 66
A Prova do Teorema 3.1 69
B C´odigos Raptor 70
B.1 C´odigos Raptor n˜ao-sistem´aticos 70
B.2 Codifica¸c˜ao Raptor sistem´atica. 72
B.3 Constru¸c˜ao de codificador e decodificador Raptor sistem´atico 74
B.4 Implementa¸c˜ao dos c´odigos Raptor n˜ao-sistem´aticos 75
B.4.1 Constru¸c˜ao do pr´e-c´odigo LDPC 76
B.4.2 Constru¸c˜ao do c´odigo LT interno 78
B.5 Resultados obtidos das simula¸c˜oes 79
Lista de figuras
1.1 Diagrama em Blocos de um Sistema de comunica¸c˜oes. 14
1.2 Canal quatern´ario com apagamento. 16
2.1 Grafo resultante da codifica¸c˜ao. 24
2.2 Grafo do processo de decodifica¸c˜ao 26
2.3 Processo LT 29
2.4 A distribui¸c˜ao S´oliton Ideal ρ(d) para o caso k = 10000. 31
2.5 A distribui¸c˜ao S´oliton Ideal ρ(d) e a fun¸c˜ao positiva τ(d) para o
caso k = 10
4
, c = 0.2 e δ = 0.1. 32
2.6 A distribui¸c˜ao S´oliton Robusta µ(d) para o caso k = 10
4
, c = 0.2
e δ = 0.1. 32
2.7 Histograma do n´umero de s´ımbolos codificados necess´arios para a
decodifica¸c˜ao com sucesso para distintos valores de c (k = 1000,
δ = 0.1). 35
2.8 Histograma do n´umero de s´ımbolos codificados necess´arios para a
decodifica¸c˜ao com sucesso para distintos valores de δ (k = 1000,
c = 0.03). 36
2.9 Desempenho do c´odigo LT em canais ideais. 38
2.10 Sistema com c´odigos detetores de erros (CDE) usados em conjunto
com c´odigos LT. 39
2.11 Desempenho do c´odigo LT em canais com apagamento. 40
3.1 Distribui¸c˜ao S´oliton Ideal: primeira itera¸c˜ao. 46
3.2 Distribui¸c˜ao S´oliton Ideal: segunda itera¸c˜ao. 46
3.3 Desempenho das distribui¸c˜oes S´oliton Robusta com parˆametros
c = 0.03 e δ = 0.1 e S´oliton Ideal. 47
3.4 Distribui¸c˜ao S´oliton Robusta: primeira itera¸c˜ao. 50
3.5 Distribui¸c˜ao S´oliton Robusta: segunda itera¸c˜ao. 50
4.1 A distribui¸c˜ao S´oliton Robusta Melhorada para o caso k = 10000,
c = 0.2 e δ = 0.1 53
4.2 Histograma do n´umero de s´ımbolos necess´arios para a decodi-
fica¸c˜ao com sucesso de um c´odigo LT com distribui¸c˜ao S´oliton
Robusta Melhorada (k = 1000, c = 0.03 e δ = 0.1). 54
4.3 Histograma do n´umero de s´ımbolos necess´arios para a decodi-
fica¸c˜ao com sucesso de um c´odigo LT com distribui¸c˜ao S´oliton
Robusta (k = 1000, c = 0.03 e δ = 0.1). 54
4.4 Desempenho das distribui¸c˜oes S´oliton Robusta e S´oliton Robusta
Melhorada para um c´odigo LT(1000,1300) com parˆametros c =
0.03 e δ = 0.1. 55
4.5 A distribui¸c˜ao S´oliton Robusta Truncada Ω(d) para o caso k =
10000, c = 0.2, δ = 0.1 e γ = 6. 57
4.6 Reagrupamento bidimensional dos s´ımbolos de entrada s
k
. 57
4.7 Processo de codifica¸c˜ao e decodifica¸c˜ao bidimensional. 58
4.8 Compara¸c˜ao de desempenho entre as configura¸c˜oes que usam a
distribui¸c˜ao SR. Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1
e γ = 6. 61
4.9 Overhead () requerido para uma decodifica¸c˜ao bem sucedida, em
fun¸c˜ao de P
a
. Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1
e γ = 6. 61
4.10 Compara¸c˜ao de desempenho entre as configura¸c˜oes que usam a
distribui¸c˜ao SRM. Parˆametros utilizados: k = 1000, c = 0.03,
δ = 0.1 e γ = 6. 62
4.11 Taxa de apagamento de s´ımbolo em fun¸c˜ao da capacidade do canal
(1−P
a
). Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1, γ = 6
e = 30%. 63
B.1 Etapa de Pr´e-codifica¸c˜ao em c´odigos Raptor. 71
B.2 Diagrama em bloco da codifica¸c˜ao Raptor sistem´atica. 74
B.3 Restri¸c˜oes na codifica¸c˜ao do c´odigo Raptor sistem´atico. 74
B.4 Diagrama em blocos do c´odigo Raptor. 75
B.5 Processo de codifica¸c˜ao do c´odigo Raptor. 75
B.6 Grafo de Tanner correspondente `a matriz de paridade H de (B-13). 77
B.7 Probabilidade de falha em fun¸c˜ao do overhead. Canal ideal. 80
B.8 Taxa de apagamento de s´ımbolo em fun¸c˜ao do overhead. Canal
BEC com P
a
= 0, 04 80
B.9 Compara¸c˜ao de desempenho entre c´odigos LT com distribui¸c˜ao
SRM e c´odigos Raptor. Canal Ideal. 81
Lista de tabelas
2.1 Processo de codifica¸c˜ao. 24
2.2 N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de c (k = 1000, δ = 0.1). 35
2.3 N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de δ (k = 1000, c = 0.03). 36
2.4 N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de k (c = 0.03, δ = 0.1) 38
4.1 Configura¸c˜oes Bidimensionais 59
Sum´ario das nota¸c˜oes
k N´umero de s´ımbolos de entrada
n N´umero de s´ımbolos codificados
R Taxa do c´odigo
ρ(d) Distribui¸c˜ao S´oliton Ideal
τ(d) Fun¸c˜ao positiva complementaria
µ(d) Distribui¸c˜ao S´oliton Robusta
¯
R N´umero m´edio de s´ımbolos codificados de grau um
c Parˆametro da distribui¸c˜ao S´oliton Robusta
δ Limite superior da probabilidade de falha na decodifica¸c˜ao de c´odigos LT
β Constante de normaliza¸c˜ao
P
a
Probabilidade de apagamento do canal BEC
(1 + ) Overhead do c´odigo LT
h
t
(d) N´umero de s´ımbolos codificados de grau d na t-´esima itera¸c˜ao
ν Fator complemento para obter a distribui¸c˜ao S´oliton Robusta Melhorada
µ(d, γ, ν) Distribui¸c˜ao S´oliton Robusta Truncada
β
Constante de normaliza¸c˜ao
γ Fator de truncamento
(1 + ε
Raptor
) Overhead do c´odigo Raptor
m N´umero de s´ımbolos de paridade do pr´e-c´odigo LDPC
w
c
Peso das colunas da matriz de paridade H do c´odigo LDPC
w
r
Peso das linhas da matriz de paridade H do c´odigo LDPC
L N´umero de s´ımbolos pr´e-codificados do c´odigo Raptor
Ω
D
(x) Distribui¸c˜ao de graus para c´odigos Raptor
1
Introdu¸c˜ao
1.1
Motiva¸c˜ao
Um problema comum que existe em um sistema de comunica¸c˜ao ´e o
envio de informa¸c˜ao atrav´es de um canal com apagamento, em que certos
s´ımbolos recebidos s˜ao distintos de todos os poss´ıveis s´ımbolos transmitidos
(tais s´ımbolos irreconhec´ıveis s˜ao ditos apagados). Um exemplo de um sistema
de comunica¸c˜ao em que ocorre tal problema ´e a comunica¸c˜ao realizada por
meio da Internet, na qual a troca de informa¸c˜ao ´e feita atrav´es de pacotes.
Inicialmente, a estrat´egia mais utilizada para solucionar o problema de
perda de pacotes ´e empregar um canal de retorno (feedback channel) entre o
receptor e o transmissor, para controlar a retransmiss˜ao dos pacotes corrom-
pidos ou perdidos. Este m´etodo de controle de erros na transmiss˜ao de dados
´e conhecido como ARQ (Automatic Repeat Request) [29]. Existem situa¸c˜oes
em que tal estrat´egia n˜ao ´e apropriada, como por exemplo a transmiss˜ao
do tipo multicast, j´a que, requer-se um grande n´umero de retransmiss˜oes
para que os receptores sejam capazes de receber a informa¸c˜ao original por
completo [2, 5, 26]. Recentemente foi proposta uma solu¸c˜ao para o problema
de transmiss˜ao de informa¸c˜ao atrav´es de canais com apagamento, usando uma
classe c´odigos conhecida por “c´odigos fontanais” [7].
A primeira implementa¸c˜ao pr´atica de c´odigos fontanais inventada por
M. Luby, ´e conhecida como c´odigos LT (Luby Transform) [6]. C´odigos LT s˜ao
capazes de recuperar, com probabilidade maior do que (1 − δ), um conjunto
de k s´ımbolos de entrada a partir de quaisquer k + O(
√
k ln
2
(k/δ)) s´ımbolos
codificados recebidos — para isso uma m´edia de O(k ln(k/δ)) opera¸c˜oes
1
por
s´ımbolo s˜ao realizadas.
1
considera-se que uma opera¸c˜ao corresponde a uma opera¸c˜ao ou-exclusivo (XOR) ou
uma opera¸c˜ao que copia um s´ımbolo de um registrador para outro.
Cap´ıtulo 1. Introdu¸c˜ao 14
Posteriormente, foram propostos os c´odigos Raptor por Shokrollahi [21],
que s˜ao uma extens˜ao de c´odigos LT. A id´eia principal do c´odigo Raptor ´e pri-
meiro codificar a mensagem original (s´ımbolos de entrada) usando um c´odigo
de bloco de taxa fixa (por exemplo, um c´odigo LDPC), e em seguida, codificar
esses novos s´ımbolos (s´ımbolos intermedi´arios) usando um c´odigo LT.
C´odigos Fontanais s˜ao uma classe de c´odigos criados para a transmiss˜ao
de dados de maneira eficiente atrav´es de canais com apagamento. Estes c´odigos
s˜ao capazes de gerar um n´umero ilimitado de s´ımbolos codificados a partir dos
dados de entrada, por esta raz˜ao tais c´odigos s˜ao denominados, na literatura
inglesa, por “rateless codes” — nesta disserta¸c˜ao denominaremos tais c´odigos
por c´odigos com taxa vers´atil [2, 6, 26].
1.2
Sistema de Comunica¸c˜ao
Em um sistema de comunica¸c˜ao, o objetivo consiste em transmitir uma
mensagem atrav´es de um canal de comunica¸c˜ao, de modo que o receptor seja
capaz de determinar esta mensagem com confiabilidade, diante das adver-
sidades impostas pelo canal. No entanto, as comunica¸c˜oes reais s˜ao sempre
afetados por ru´ıdo, que ´e sem d´uvida um dos fatores b´asicos que limitam a
taxa das comunica¸c˜oes.
A estrat´egia utilizada para garantir uma transmiss˜ao fidedigna de
informa¸c˜ao atrav´es de canais n˜ao ideais ´e codificar a informa¸c˜ao a ser trans-
mitida, inserindo redundˆancia, para reduzir os efeitos do ru´ıdo sobre a
mensagem original.
O modelo b´asico de sistemas de comunica¸c˜oes utilizado no presente
trabalho, seguindo tal abordagem, encontra-se ilustrado na Figura 1.1.
Fonte Usu´ario
✲ ✲ ✲ ✲
Codificador
s x
y
ˆs
Canal Ruidoso Decodificador
Figura 1.1: Diagrama em Blocos de um Sistema de comunica¸c˜oes.
Neste modelo, ´e suposto que a fonte utilizada ´e bin´aria, e que portanto a
mensagem s que se deseja transmitir, consiste de um bloco de bits de tamanho
k, representada pelo vetor:
s =
s
1
, s
2
, . . . , s
k
. (1-1)
Cap´ıtulo 1. Introdu¸c˜ao 15
A mensagem s ´e enviada a um codificador que adicionando redundˆancia, a
transforma em uma mensagem codificada x que ´e representada pelo vetor:
x =
x
1
, x
2
, . . . , x
n
(1-2)
sendo esta enviada atrav´es do canal. Diz-se que a raz˜ao R = k/n ´e a Taxa de
Transmiss˜ao de Informa¸c˜ao do codificador. A mensagem recebida y `a sa´ıda do
canal, pode n˜ao ser uma r´eplica da mensagem codificada enviada x, ou seja,
y = x. O decodificador ent˜ao usa a redundˆancia introduzida pelo codificador
para recuperar, desejavelmente sem erro, a mensagem original s.
A teoria para o desenvolvimento de bons c´odigos corretores de erros
foi introduzida por Claude Shannon, atrav´es do Teorema de Codifica¸c˜ao de
Canal, que garante ser poss´ıvel realizar transmiss˜oes com probabilidades de
erro arbitrariamente baixas, desde que a taxa de codifica¸c˜ao seja menor que a
capacidade do canal [20].
1.3
Modelo de canais com apagamentos
Canais com apagamento foram introduzidos por P. Elias [4], na qual um
pacote ´e recebido sem erro ou ´e convertido em um apagamento.
Em um canal com apagamento, o conjunto B = {a
0
, . . . , a
q−1
, a
q
= ?},
de poss´ıveis s´ımbolos `a sa´ıda do canal, possui um s´ımbolo a mais do que o
alfabeto de entrada A = {a
0
, . . . , a
q−1
}. O alfabeto de sa´ıda B ´e composto
pelos “q” s´ımbolos de A e por um s´ımbolo adicional que corresponde ao
“s´ımbolo apagado”denotado como “?”.
´
E importante mencionar que existe
uma probabilidade de transi¸c˜ao que relaciona um s´ımbolo de entrada e um
s´ımbolo de sa´ıda do canal, a qual ´e definida como
P (Y
j
= a
m
| X
j
= a
i
) =
1 − P
a
, m = i ∈ {0, q − 1}
P
a
, m = q
Um canal ruidoso (que introduz erro) usado com um bom c´odigo detetor
de erro, pode ser aproximado por um com canal com apagamento, ou seja,
caso um pacote de informa¸c˜ao recebido contenha erros detect´aveis, pelo c´odigo
detetor de erro em uso, o pacote ´e descartado e interpretado como apagado.
Um modelo de canal com apagamento formado por um alfabeto de
Cap´ıtulo 1. Introdu¸c˜ao 16
entrada n˜ao-bin´ario de tamanho q = 2
, onde ´e o n´umero de bits de cada
pacote que vai ser transmitido, gerado pela fonte de informa¸c˜ao, ´e mostrado
na Figura 1.2. Nela encontra-se ilustrado um canal quatern´ario (q = 2
2
) com
apagamento, o qual possui uma probabilidade (1 −P
a
) de transmitir o pacote
de entrada sem erro, e uma probabilidade P
a
de entregar ao receptor o s´ımbolo
“?”, o qual significa um apagamento.
Entrada Sa´ıda
(1 − P
a
)
P
a
00
01
10
11
00
01
10
11
?
✲
✲
✲
✲
❘
s
❥
③
Figura 1.2: Canal quatern´ario com apagamento.
A capacidade de um canal com apagamento q-´ario ´e:
C = (1 − P
a
) bits/uso-do-canal (1-3)
Os c´odigos de bloco que s˜ao tradicionalmente utilizados como c´odigos detetores
de erros, para detectar s´ımbolos n˜ao reconhec´ıveis, produzindo assim um canal
com apagamento, s˜ao os c´odigos RS (Reed-Solomon) [16]. Mais recentemente
surgiram os c´odigos Tornado [27] — estes, c´odigos de taxa fixa (R = k/n),
apresentam severas limita¸c˜oes, por exemplo, k e n s˜ao limitados a valores
razoavelmente pequenos. Al´em disso, ao contr´ario do que acontece com c´odigos
fontanais, para o uso de c´odigos RS ou c´odigos Tornado deve-se estimar a
probabilidade P
a
de apagamento do canal e determinar a taxa R do c´odigo,
antes que o processo de codifica¸c˜ao tenha in´ıcio [8].
1.4
Fontanas Digitais
O conceito de Fontana Digital (Digital Fountain) introduzido em [26]
surgiu da inten¸c˜ao de se desenvolver um esquema de codifica¸c˜ao no qual, a
partir de um subconjunto qualquer de pacotes codificados com cardinalidade
igual `a do conjunto de pacotes que constituem os dados originais, o receptor
Cap´ıtulo 1. Introdu¸c˜ao 17
seja capaz de recuperar a mensagem originalmente transmitida. O nome
fontana digital surgiu a partir da observa¸c˜ao de que o codificador pode ser
visto como um chafariz que jorra um n´umero arbitrariamente grande de gotas
de ´agua (pacotes codificados
2
).
Uma defini¸c˜ao de Fontana Digital Ideal ´e apresentada a seguir.
Defini¸c˜ao 1.1 (Fontana Digital Ideal) (Ideal Digital Fountain)
Uma Fontana Digital Ideal ´e um esquema capaz de produzir, a partir de k
s´ımbolos de entrada s, uma seq¨uˆencia de s´ımbolos codificados x que obedece as
seguintes propriedades [10],
1. O n´umero de s´ımbolos codificados denotado por |x| ´e um n´umero arbi-
trariamente grande (possivelmente infinito).
2. Existe um receptor capaz de reconstruir a mensagem original s de
tamanho k, a partir de qualquer conjunto {x
i
1
, x
i
2
, . . . , x
i
j
, . . . , x
i
k
} de k
s´ımbolos codificados. (Essa reconstru¸c˜ao deve ser r´apida, de preferˆencia
linear em k).
Os c´odigos LT e c´odigos Raptor s˜ao chamados c´odigos fontanais, j´a que
eles s˜ao uma boa aproxima¸c˜ao para o conceito de fontanas digitais, no sentido
que o n´umero de pacotes necess´arios para uma decodifica¸c˜ao bem sucedida
aproxima-se do valor de k.
A seguir apresenta-se uma lista com v´arios m´etodos de transmiss˜ao de
informa¸c˜ao onde o uso dos c´odigos fontanais ´e recomendado. Estes exem-
plos [10] indicam a importˆancia dos c´odigos fontanais que s˜ao o objeto de
estudo desta disserta¸c˜ao.
Multicast. En uma transmiss˜ao multicast, uma fonte envia arquivos para um
conjunto determinado de receptores. A principal vantagem de utilizar
fontanas digitais neste tipo de transmiss˜ao ´e eliminar a necessidade de
retransmiss˜ao. Por exemplo, se um usu´ario deixa de receber um deter-
minado pacote, ele n˜ao precisa pedir retransmiss˜ao do mesmo, j´a que,
qualquer conjunto de s´ımbolos de sa´ıda, de cardinalidade igual `a cardi-
nalidade do arquivo original (conjunto de s´ımbolos de entrada) pode ser
2
Neste trabalho usaremos indistintamente os termos s´ımbolos de sa´ıda, s´ımbolos codifi-
cados e pacotes de sa´ıda. De forma an´aloga, os termos s´ımbolos de entrada ou pacote de
entrada
Cap´ıtulo 1. Introdu¸c˜ao 18
utilizado para recuperar o arquivo enviado.
Outra vantagem das fontanas digitais ´e que se torna trivial trabalhar
com receptores operando a diferentes taxas de recep¸c˜ao. Por exemplo,
se dois receptores que tˆem diferentes taxas de download, e compartilham
um mesmo enlace — seq¨uˆencia de links, exceto o ´ultimo link do percurso
de roteamento, os pacotes podem ser enviados `a taxa mais alta ao longo
do caminho, e s˜ao diminu´ıdos no ´ultimo link, ajustando-se assim `a taxa
do receptor mais lento. De maneira similar, ´e poss´ıvel que dois receptores
comecem a efetuar downloads em momentos diferentes, j´a que a ordem
na qual s˜ao recebidos os pacotes n˜ao importa.
Transmiss˜ao de v´ıdeo em tempo real. Para realizar uma transmiss˜ao em
tempo real, a estrat´egia mais utilizada consiste em segmentar o arquivo
original em v´arias partes. Enquanto a primeira parte ´e executada a
segunda ´e baixada (downloading) e assim por diante. Para fazer uso
desta estrat´egia deve-se ter em conta algumas considera¸c˜oes como por
exemplo: o tamanho dos segmentos, a raz˜ao entre a taxa de download e
a taxa de execu¸c˜ao, etc.
Recep¸c˜ao paralela de arquivos. A recep¸c˜ao em paralelo de arquivos pro-
venientes de varias fontes distintas ´e outra aplica¸c˜ao em que o uso de
fontanas digitais ´e adequado. Nesta aplica¸c˜ao, cada fonte independen-
temente, pode produzir uma sequˆencia infinita de pacotes codificados.
Como a disponibilidade de pacotes codificados ´e essencialmente infinita, a
possibilidade de colis˜ao (quando o mesmo pacote ´e enviado por m´ultiplas
fontes) ´e nula. Al´em disso, o receptor pode encerrar a se¸c˜ao de recep¸c˜ao
ap´os receber o n´umero de pacotes suficientes, sem preocupa¸c˜ao alguma
de onde os pacotes s˜ao provenientes.
1.5
Objetivos e organiza¸c˜ao do trabalho
Neste trabalho, apresentamos um estudo sobre o esquema de codifica¸c˜ao
fontanal, para canais com apagamento, conhecido como c´odigo LT. Outro
c´odigo da fam´ılia de c´odigos fontanais tamb´em abordado neste trabalho forma
os c´odigos Raptor. O estudo inclui ainda a an´alise de diferentes distribui¸c˜oes
de graus utilizadas por estes esquemas: a distribui¸c˜ao S´oliton Robusta, a
distribui¸c˜ao S´oliton Robusta Melhorada, a distribui¸c˜ao S´oliton Robusta Trun-
cada para c´odigos LT sistem´aticos e a distribui¸c˜ao de Shokrollahi usada pelos
c´odigos Raptor.
´
E proposto tamb´em um esquema de c´odigos LT Bidimensio-
nais com o intuito de encontrar uma implementa¸c˜ao mais eficiente do que a
Cap´ıtulo 1. Introdu¸c˜ao 19
implementa¸c˜ao dos c´odigos LT cl´assicos.
Esta disserta¸c˜ao encontra-se organizada em cinco cap´ıtulos e dois
apˆendices. As referˆencias bibliogr´aficas localizam-se imediatamente ap´os o
Cap´ıtulo 5. Em resumo, o conte´udo apresentado ´e o seguinte.
No Cap´ıtulo 2, apresentam-se os principais conceitos relacionados aos
c´odigos LT, seu processo de codifica¸c˜ao e decodifica¸c˜ao. A forma de escolha
dos parˆametros envolvidos na distribui¸c˜ao de graus S´oliton Robusta e an´alise
de desempenho dos c´odigos LT em termos destes parˆametros s˜ao examinados.
No Cap´ıtulo 3 ´e analisado o processo de constru¸c˜ao de uma boa dis-
tribui¸c˜ao de graus para os c´odigos LT cl´assicos, al´em de uma compara¸c˜ao
de desempenho destes c´odigos quando a distribui¸c˜ao S´oliton Ideal e S´oliton
Robusta s˜ao usadas.
No Cap´ıtulo 4 s˜ao apresentadas duas distribui¸c˜oes de graus recentemente
propostas: as distribui¸c˜oes S´oliton Robusta Melhorada e S´oliton Robusta Trun-
cada (esta ´ultima desenvolvida para uso com c´odigos LT sistem´aticos), com
intuito de melhorar ainda mais o desempenho dos c´odigos LT. Al´em disso, um
modelo de c´odigos LT Bidimensionais ´e aqui introduzido.
No Cap´ıtulo 5, apresentamos as conclus˜oes deste trabalho e algumas
sugest˜oes para trabalhos futuros.
Nos Apˆendices A e B, apresenta-se a prova do Teorema 3.1 e um estudo
detalhado sobre os c´odigos Raptor.
2
C´odigos LT
Os c´odigos LT (Luby Transform), propostos por Michael Luby em 2002
[6], foram a primeira implementa¸c˜ao do conceito de fontana digital (digital
fountain) com tempo de codifica¸c˜ao e decodifica¸c˜ao vi´avel. As fontanas digitais
s˜ao sistemas que produzem `a sua sa´ıda, a partir de um bloco (ou arquivo)
s =
s
1
, s
2
, . . . , s
k
com k s´ımbolos de entrada gerados por uma fonte de informa¸c˜ao, um bloco
x =
x
1
, . . . , x
j
, . . . , x
n
,
potencialmente muito grande, com n s´ımbolos codificados.
O fato dos c´odigos LT se basearem em opera¸c˜oes XOR permite a
constru¸c˜ao de codificadores e decodificadores que operam em altas veloci-
dades [19]. Os c´odigos LT foram originalmente concebidos para canais com
apagamento (Erasure Channel), livres de erros, isto ´e, canais em que o alfa-
beto de entrada ´e o conjunto de s´ımbolos A = {a
0
, . . . , a
q−1
} e o alfabeto de
sa´ıda ´e o conjunto de s´ımbolos B = {a
0
, . . . , a
q−1
, a
q
} e a probabilidade de um
s´ımbolo transmitido ser recebido corretamente ´e (1−P
a
) e de ser apagado ´e P
a
.
A sa´ıda do codificador LT (entrada do canal portanto) ´e uma sequˆencia
de v.a.’s (vari´aveis aleat´orias) independentes X = X
1
, . . . , X
k
, . . . , X
n
e tem-se
que a probabilidade condicional que relaciona a v.a. X
j
`a entrada do canal com
a v.a. Y
j
, `a sa´ıda do canal, tamb´em designada por probabilidade de transi¸c˜ao
do canal, ´e
P (Y
j
= a
m
| X
j
= a
i
) =
1 − P
a
, m = i ∈ {0, q − 1}
P
a
, m = q
Em geral tem-se q = 2
e, neste trabalho, sem perda de generalidade,
considera-se o caso = 1, e que, portanto, a transmiss˜ao ´e feita atrav´es de um
BEC (Binary Erasure Channel). Ainda por simplicidade, para representar o
Cap´ıtulo 2. C´odigos LT 21
alfabeto de entrada e sa´ıda do canal, a seguinte nota¸c˜ao ´e utilizada
A = {a
0
, a
1
} = {0, 1} e, B = {a
0
, a
1
, a
2
} = {0, 1, ?}.
Os c´odigos LT s˜ao tais que cada s´ımbolo codificado t
j
´e estatisticamente
independente de todos os demais s´ımbolos codificados e o conjunto de k
s´ımbolos de entrada originais pode ser recuperado, com probabilidade maior
que (1−δ), a partir de quaisquer k +O(
√
k ln
2
(k/δ)) s´ımbolos codificados, com
uma m´edia de O(k ln(k/δ)) opera¸c˜oes por s´ımbolo [6]. O n´umero de s´ımbolos
codificados que podem ser gerados a partir dos dados de entrada ´e potencial-
mente ilimitado. Por isso, os c´odigos LT s˜ao ditos c´odigos de taxa vers´atil
1
(rateless). Assim, independentemente do modelo de perdas do canal em uso,
o codificador simplesmente gera e envia dados at´e que um n´umero suficiente
seja recebido pelo decodificador para a recupera¸c˜ao da mensagem original. A
caracter´ıstica do canal somente influencia no tempo necess´ario at´e que sejam
recebidos s´ımbolos de sa´ıda em quantidade suficiente para que a decodifica¸c˜ao
seja realizada com sucesso. Em qualquer canal com apagamento, os c´odigos
LT s˜ao quase ´otimos no sentido de que o decodificador pode recuperar a
mensagem original formada por k s´ımbolos de entrada a partir de quaisquer
(1 + )k s´ımbolos codificados, onde 0 < < 1. Considera-se um c´odigo ´otimo,
aquele que consegue recuperar a mensagem original (formada por k s´ımbolos
de entrada), a partir de qualquer subconjunto de k s´ımbolos de sa´ıda dentre
os n gerados pelo codificador [9]. Por serem quase ´otimos e por sua eficiˆencia
aumentar com o crescimento do comprimento do bloco de entrada do codifi-
cador, os c´odigos LT s˜ao denominados universais [6].
O objetivo deste cap´ıtulo ´e o estudo dos algoritmos de codifica¸c˜ao e
decodifica¸c˜ao, a escolha dos parˆametros da distribui¸c˜ao S´oliton Robusta e a
an´alise do desempenho dessa classe de c´odigo.
2.1
Codifica¸c˜ao
Nesta se¸c˜ao ´e descrito o processo de codifica¸c˜ao utilizando c´odigos LT.
Considere que a mensagem original s consiste de k s´ımbolos de informa¸c˜ao
denotados por s
1
, s
2
, ..., s
k
. Em geral, s
i
∈ GF (2
), mas por simplicidade
considera-se um alfabeto de entrada bin´ario, ou seja, = 1.
`
A sa´ıda do
codificador um vetor x de dimens˜ao n ´e obtido.
´
E importante ressaltar que
1
Na verdade, para um dado usu´ario, os c´odigos LT s˜ao c´odigos de taxa vari´avel, sendo o
n´umero de s´ımbolos codificados n recebidos pelo usu´ario vari´avel de acordo com o n´umero
de s´ımbolos necess´arios para que a decodifica¸c˜ao ocorra com sucesso.
Cap´ıtulo 2. C´odigos LT 22
a regra de forma¸c˜ao de x
n
permite que o n´umero de s´ımbolos de x, n = |x|,
possa ser aumentado indefinidamente de forma que a taxa deste c´odigo,
R =
k
n
,
pode tender para zero.
Para descrever o processo de codifica¸c˜ao considere inicialmente uma
sequˆencia {D
1
, . . . , D
n
} de v.a.’s discretas i.i.d.’s em que D
j
∈ Z
k
= {1, . . . , k}.
Considere tamb´em que a fun¸c˜ao µ com
µ(d) = P (D
j
= d), d ∈ Z
k
.
´e a Distribui¸c˜ao de Probabilidades (DP) associada `a v.a. D
j
.
Para uma dada sequˆencia de informa¸c˜ao s = ( s
1
, . . . , s
k
), considerando
que {d
1
, . . . , d
n
} ´e uma realiza¸c˜ao da sequˆencia aleat´oria {D
1
, . . . , D
n
}, tem-se
ent˜ao que cada s´ımbolo codificado x
j
´e produzido de forma aleat´oria de acordo
com a seguinte equa¸c˜ao
x
j
=
d
j
=1
s
i
(j)
(2-1)
onde
corresponde `a adi¸c˜ao m´odulo-2 dos termos do somat´orio.
´
E importante ressaltar que os valores dos ´ındices {i
1
(j), i
2
(j), . . . , i
d
j
(j)}
das d
j
parcelas {s
i
1
(j)
, s
i
2
(j)
, . . . , s
i
d
j
(j)
} em (2-1) s˜ao realiza¸c˜oes da sequˆencia
de v.a.’s I
1
, . . . , I
d
j
onde I
1
∈ Z
k
´e uma v.a. discreta com DP uniforme, ou
seja, para i
1
∈ Z
k
, tem-se
P (I
1
= i
1
) =
1
k
.
A v.a. I
2
´e tamb´em uma v.a. discreta com DP-condicional uniforme, definida
da seguinte maneira para (i
1
, i
2
) ∈ Z
2
k
,
P (I
2
= i
2
| I
1
= i
1
) =
1
k−1
i
2
= i
1
0 i
2
= i
1
A v.a. I
3
tem DP-condicional uniforme, definida para (i
1
, i
2
, i
3
) ∈ Z
3
k
,
P (I
3
= i
3
| (I
1
, I
2
) = (i
1
, i
2
)) =
1
k−2
i
3
/∈ {i
1
, i
2
}
0 i
3
∈ {i
1
, i
2
},
Cap´ıtulo 2. C´odigos LT 23
e, assim por diante, at´e que, para (i
1
, i
2
, . . . , i
d
j
) ∈ Z
d
j
k
, tem-se
P (I
d
j
= i
d
j
| (I
1
, . . . , I
d
j
−1
) = (i
1
, . . . , i
d
j
−1
)) =
1
k−(d
j
−1)
d
j
/∈ {i
1
, . . . , i
d
j
−1
}
0 d
j
∈ {i
1
, . . . , i
d
j
−1
}.
.
Vale observar que x = ( x
1
, . . . , x
j
, . . . , x
n
) ∈ {0, 1}
∗
, onde {0, 1}
∗
´e a
nota¸c˜ao usada para representar o conjunto de todos os blocos bin´arios.
2.2
Codificador LT como um c´odigo em grafo
Nesta se¸c˜ao o codificador LT ser´a descrito em associa¸c˜ao com um grafo G,
bi-particionado, isto ´e, um grafo em que o conjunto de n´os ´e particionado em
dois conjuntos — um conjunto E = {s
1
, . . . , s
k
} de n´os de mensagem ou n´os
de entrada e um conjunto S = {x
1
, . . . , x
n
} de n´os de verifica¸c˜ao ou n´os de
sa´ıda. A cada n´o de entrada associa-se um s´ımbolo de entrada s
i
(que ser´a
identificado, indistintamente, como n´o s
i
), e a cada n´o de sa´ıda corresponder´a
um s´ımbolo codificado x
j
(que ser´a identificado como n´o x
j
).
Note que G ´e um grafo aleat´orio em que cada n´o de sa´ıda x
j
est´a conec-
tado a d
j
n´os de entrada {s
i
1
, . . . , s
i
d
j
}, onde d
j
∈ Z
k
´e escolhido aleatoriamente
de acordo a uma DP µ(d). Tem-se assim que V
j
= {s
i
1
, . . . , s
i
d
j
} ´e o conjunto
de n´os de entrada vizinhos do n´o x
j
. O n´umero de vizinhos d
j
de um n´o de
sa´ıda x
j
ser´a referido como o grau do n´o x
j
e, a DP µ(d) ser´a designada por
distribui¸c˜ao de graus do c´odigo LT. Ent˜ao, o codificador LT ´e descrito a seguir:
• Para cada s´ımbolo codificado x
j
, escolhe-se aleatoriamente e segundo a
DP µ(d), um n´umero d
j
.
• Escolhe-se aleatoriamente, um conjunto {s
i
1
, . . . , s
i
d
j
}, de d
j
s´ımbolos de
entrada distintos (em posi¸c˜oes {i
1
, . . . , i
d
j
} escolhidas de acordo com uma
distribui¸c˜ao uniforme), como s´ımbolos de entrada vizinhos do s´ımbolo
codificado x
j
.
• O valor do s´ımbolo codificado ´e
x
j
= s
i
1
⊕ . . . ⊕ s
i
d
j
,
onde ⊕ representa a adi¸c˜ao bit a bit, modulo-2, desses d
j
s´ımbolos.
Neste processo de codifica¸c˜ao duas distribui¸c˜oes de probabilidades s˜ao
envolvidas: a distribui¸c˜ao de graus para determinar o grau de cada s´ımbolo
codificado (a distribui¸c˜ao S´oliton Robusta sendo a mais recomendada) e, outra,
Cap´ıtulo 2. C´odigos LT 24
distribui¸c˜ao uniforme para escolher os s´ımbolos de entrada que formar˜ao o
conjunto de vizinhos do s´ımbolo codificado.
A seguir, para descrever tal processo, apresentamos um exemplo.
Exemplo 2.1 Considere uma mensagem formada por 5 s´ımbolos de entrada
s
1
s
2
s
3
s
4
s
5
= 10011, onde, por simplicidade, cada s´ımbolo de entrada tem
comprimento de apenas 1 “bit”. Realizamos a codifica¸c˜ao dessa mensagem
gerando seis s´ımbolos de sa´ıda x
1
x
2
x
3
x
4
x
5
x
6
. Assim, o processo de codifica¸c˜ao ´e
composto por seis etapas, uma para cada s´ımbolo de sa´ıda gerado. A tabela (2.1)
mostra o resultado do processo de codifica¸c˜ao.
Tabela 2.1: Processo de codifica¸c˜ao.
s´ımbolo grau (d
j
) vizinhos valor
x
1
2 s
1
s
2
s
1
⊕ s
2
= 1
x
2
3 s
1
s
2
s
4
s
1
⊕ s
2
⊕ s
4
= 0
x
3
4 s
1
s
2
s
3
s
5
s
1
⊕ s
2
⊕ s
3
⊕ s
5
= 0
x
4
4 s
1
s
3
s
4
s
5
s
1
⊕ s
3
⊕ s
4
⊕ s
5
= 1
x
5
1 s
5
s
5
= 1
x
6
2 s
2
s
5
s
2
⊕ s
5
= 1
O grafo resultante apresentado na Figura 2.1, ilustra o processo de
codifica¸c˜ao do Exemplo 2.1 — os s´ımbolos codificados, x
n
, n´os de sa´ıda, e suas
respectivas conex˜oes com os s´ımbolos de entrada, s
k
, n´os de entrada, formam
um grafo bipartido. Cada s´ımbolo de sa´ıda ´e conectado, atrav´es de um ramo,
aos s´ımbolos de entrada vizinhos.
s
5
s
1
s
4
s
3
s
2
1
x
2
x
3
x
4
x
5
x
6
x
Figura 2.1: Grafo resultante da codifica¸c˜ao.
Cap´ıtulo 2. C´odigos LT 25
2.3
Decodifica¸c˜ao
Para recuperar os k s´ımbolos de entrada da mensagem original, sup˜oe-se
que o decodificador conhece o grafo G, isto ´e, o grau e o conjunto de vizinhos de
cada s´ımbolo codificado. Neste processo de decodifica¸c˜ao, utiliza-se a mesma
nota¸c˜ao: os s´ımbolos codificados (x
n
) formar˜ao os n´os de sa´ıda e os s´ımbolos
de entrada (s
k
) formar˜ao os n´os de entrada. O algoritmo de decodifica¸c˜ao de
c´odigos LT ´e descrito a seguir:
1. Encontrar um n´o de sa´ıda x
n
que esteja conectado a apenas um s´ımbolo
de entrada s
k
, caso n˜ao exista tal n´o de sa´ıda, o processo de decodifica¸c˜ao
falha, sendo necess´ario receber mais s´ımbolos codificados antes de fazer
uma nova tentativa de decodifica¸c˜ao.
• Fazer s
k
= x
n
,
• Somar em modulo-2, o valor de s
k
a todos os n´os de sa´ıda restantes
x
n
que estejam conectados a s
k
,
• Remover todas as conex˜oes que chegam ao s´ımbolo de entrada s
k
.
Como resultado, o grau de tais n´os de sa´ıda ´e reduzido em um.
2. Repetir (1) at´e que todos os s
k
s´ımbolos de entrada sejam determinados.
O processo de decodifica¸c˜ao correspondente ao Exemplo 2.1 est´a ilus-
trado na Figura 2.2. Existem cinco s´ımbolos de entrada (indicados pelos n´os
de entrada superiores) que inicialmente est˜ao apagados, e, seis s´ımbolos de
sa´ıda (indicados pelos n´os de sa´ıda inferiores), os quais tem o seguinte valor
inicialmente x
1
x
2
x
3
x
4
x
5
x
6
= 100111.
1. Na primeira itera¸c˜ao, o ´unico n´o de sa´ıda conectado a apenas um s´ımbolo
de entrada ´e x
5
(Fig. 2.2-a).
2. Faz-se ent˜ao s
5
= x
5
e elimina-se o n´o de sa´ıda x
5
(Fig. 2.2-b).
3. Adiciona-se o valor de s
5
aos n´os de sa´ıda que est˜ao ligados ao mesmo,
desconectando s
5
do grafo (Fig. 2.2-c).
4. No inicio da segunda itera¸c˜ao, o sexto n´o de sa´ıda est´a ligado apenas a
s
2
(Fig. 2.2-c).
5. Faz-se ent˜ao s
2
= x
6
e elimina-se o n´o de sa´ıda x
6
(Fig. 2.2-d).
6. Adiciona-se o valor de s
2
aos trˆes n´os de sa´ıda ligados a ele, desconec-
tando s
2
do grafo (Fig. 2.2-e).
Cap´ıtulo 2. C´odigos LT 26
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
d)
e)
f)
c)
1 1
1 1
0
0
g)
1
1 11
0
0
h)
1 11
0
i)
S1 S2 S3 S4 S5
1 11
0 0
j)
S1 S2 S3 S4 S5
1
a)
b)
00
1
x
2
x
3
x
4
x
5
x
6
x
1
x
2
x
3
x
4
x
6
x
1
x
2
x
3
x
4
x
1
x
2
x
3
x
4
x
6
x
1
x
2
x
3
x
4
x
2
x
3
x
4
x
2
x
3
x
4
x
3
x
4
x
3
x
4
x
Figura 2.2: Grafo do processo de decodifica¸c˜ao
Cap´ıtulo 2. C´odigos LT 27
7. No inicio da terceira itera¸c˜ao, o primeiro n´o de sa´ıda est´a ligado apenas
a s
1
(Fig. 2.2-e).
8. Faz-se ent˜ao s
1
= x
1
e elimina-se o n´o de sa´ıda x
1
(Fig. 2.2-f).
9. Adiciona-se o de valor s
1
aos trˆes n´os de sa´ıda ligados a ele, desconec-
tando s
1
do grafo (Fig. 2.2-g).
10. No inicio da quarta itera¸c˜ao, escolhe-se o segundo n´o de sa´ıda que est´a
ligado apenas a s
4
Fig. (2.2-g).
11. Faz-se ent˜ao s
4
= x
2
e elimina-se o n´o de sa´ıda x
2
(Fig. 2.2-h).
12. Adiciona-se o valor de s
4
ao n´o de sa´ıda restante ligado a ele, desco-
nectando s
4
do grafo (Fig. 2.2-i).
13. Finalmente, percebe-se que dois n´os de sa´ıda est˜ao ligado a s
3
, e ambos
atribuem o mesmo valor a tal s´ımbolo de entrada, o qual ´e restaurado
em (j).
2.3.1
O processo LT
Introduzimos a descri¸c˜ao do processo LT para descrever o projeto e
an´alise de uma boa distribui¸c˜ao de graus. O processo LT ´e uma generaliza¸c˜ao
do cl´assico processo de lan¸car bolas aleatoriamente em um conjunto de urnas.
Uma an´alise bem conhecida do processo cl´assico mostra que n = k. ln(k/δ)
bolas em m´edia, s˜ao necess´arias para garantir que cada uma das k urnas ´e
coberta pelo menos por uma bola com probabilidade maior que (1 −δ) [6]. Na
an´alise do processo LT, s´ımbolos codificados s˜ao an´alogos a bolas, e s´ımbolos
de entrada s˜ao an´alogos a urnas. O processo tem sucesso se, no final, todos os
s´ımbolos de entrada forem cobertos.
Defini¸c˜ao 2.1 (Processo LT) Todos os s´ımbolos de entrada est˜ao inicial-
mente descobertos — um s´ımbolo de entrada ´e dito coberto se, ao longo da
decodifica¸c˜ao, recebe-se um s´ımbolo codificado de grau unit´ario que o tem como
vizinho. No primeiro passo do processo LT, todos os s´ımbolos codificados com
apenas um vizinho s˜ao liberados para cobrir seu vizinho ´unico. O conjunto
de s´ımbolos de entrada cobertos que n˜ao foram ainda processados ´e chamado
“ripple” e, portanto, neste ponto todos s´ımbolos de entrada cobertos est˜ao no
“ripple”. Em cada passo subseq¨uente do processo LT, um s´ımbolo de entrada
no “ripple” ´e processado, ou seja, ele ´e removido como vizinho de todos os
Cap´ıtulo 2. C´odigos LT 28
s´ımbolos codificados que o tenham como tal; e posteriormente todos os s´ımbolos
codificados que possu´ırem apenas um vizinho s˜ao liberados para cobrir tal vi-
zinho restante. Alguns destes vizinhos podem ser s´ımbolos anteriormente des-
cobertos, fazendo que o “ripple” cres¸ca, enquanto outros que j´a foram cober-
tos n˜ao causam altera¸c˜ao no “ripple”. O processo termina quando o “ripple”
encontrar-se vazio em algum passo. O processo falha quando existe pelo menos
um s´ımbolo de entrada n˜ao-coberto ao final do processo, e tem sucesso se no
final todos os s´ımbolos de entrada estiverem cobertos.
A Figura 2.3 ilustra o processo LT para a codifica¸c˜ao do Exemplo 2.1
descrito anteriormente. Inicialmente (a) todos os s´ımbolos de entrada (urnas)
est˜ao descobertos (urnas sem bolas). No primeiro passo todos os s´ımbolos
codificados (representados por retˆangulos, as bolas dentro dos retˆangulos
representam os vizinhos do s´ımbolo codificado) com apenas um vizinho s˜ao
liberados para cobrir o mesmo (b). Em cada passo subseq¨uente, um s´ımbolo
de entrada do ripple ´e processado, ou seja, ele ´e removido como vizinho de
todos os s´ımbolos codificados que o tenham como tal, os s´ımbolos sombreados
em (c), (e), (g) e (i) indicam tal processamento. Vale mencionar que em (i)
dois s´ımbolos de entrada (s
3
e s
4
) do ripple s˜ao processados. Em (c) o ripple
´e formado por s
5
, em (e) por s
2
, em (g) por s
1
e em (i) por s
3
e s
4
, ou
seja, o conjunto de s´ımbolos de entrada cobertos mas ainda n˜ao processados.
O processo termina quando o ripple encontrar-se vazio em algum passo (j).
O processo ´e bem sucedido quando todos os s´ımbolos de entrada s˜ao cobertos,
caso contr´ario falha. No exemplo em quest˜ao o processo foi bem sucedido.
No processo cl´assico de lan¸camento de n bolas em um conjunto de k
urnas, todas as bolas s˜ao lan¸cadas ao mesmo tempo, causando problemas, j´a
que v´arias bolas podem cobrir a mesma urna, tornando necess´ario um grande
n´umero de bolas para cobrir todas as urnas. Portanto, um projeto apropriado
de uma distribui¸c˜ao de graus assegura que o processo LT libere s´ımbolos
codificados de forma incremental para cobrir todos os s´ımbolos de entrada.
Os objetivos de uma apropriada distribui¸c˜ao de graus s˜ao:
• Liberar lentamente s´ımbolos codificados enquanto o processo evolui, para
manter o ripple pequeno, de modo a evitar cobertura redundante dos
s´ımbolos de entrada no ripple por v´arios s´ımbolos codificados.
• N˜ao permitir que o ripple desapare¸ca antes que todos os s´ımbolos de
entrada estejam devidamente cobertos.
Cap´ıtulo 2. C´odigos LT 29
S2
...
...
...
...
...
...
...
S
4
S4
S4
S4
S4
S4
S4
S4
S4
S4
...
...
...
...
...
...
...
S
1
S1
S1
S3
S1
S3
...
S3
S3
S3
S4
S3
S4
S3
S3
S3
S1
S1
S1
S3
S1
S1
S1
S1
S1
S1
S4
S1
S1
...
S1
S1
...
S1
S1
...
S
1
S1
...
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2 S4S3S1 S5
S2
S3
S2
S2
S2
S4
S2
S2
S2
S2
S2
S2
S2
S2
d)
g)
j)
e)
h)
f)
i)
S3
S3
S3
S1
S1
S1
S5
S5
S5
S2
S2
S2
S2
S2
S2
S5
S5
S5
S4
S4
S4
S5
S5
...
S
1
S1
S1
S3
S3
S3
...
...
...
S
5
S5
S5
S2 S4S3S1 S5
S2 S4S3S1 S5
a) b) c)
6
x
2
x
3
x
5
x
1
x
4
x
6
x
2
x
3
x
5
x
1
x
4
x
6
x
2
x
3
x
1
x
4
x
6
x
2
x
3
x
1
x
4
x
2
x
3
x
1
x
4
x
2
x
3
x
1
x
4
x
2
x
3
x
4
x
2
x
3
x
4
x
4
x
Figura 2.3: Processo LT
Cap´ıtulo 2. C´odigos LT 30
N˜ao ´e muito dif´ıcil verificar que h´a uma correspondˆencia entre o pro-
cesso LT e o decodificador, isto ´e, um s´ımbolo codificado cobre um s´ımbolo
de entrada se e somente se o s´ımbolo codificado pode recuperar tal s´ımbolo
de entrada. Assim, o processo LT tem sucesso se, e somente se o decodifica-
dor consegue recuperar com sucesso todos os s´ımbolos de entrada do arquivo
original. O n´umero total de s´ımbolos codificados necess´arios para cobrir to-
dos os s´ımbolos de entrada no processo LT corresponde ao n´umero total de
s´ımbolos codificados necess´arios para recuperar os dados de entrada no pro-
cesso de decodifica¸c˜ao. A soma dos graus dos s´ımbolos codificados corresponde
exatamente ao n´umero total de opera¸c˜oes necess´arias para recuperar o arquivo
original.
2.4
Distribui¸c˜oes de graus
Nesta se¸c˜ao, vamos introduzir a defini¸c˜ao de duas distribui¸c˜oes de graus
utilizadas no processo de codifica¸c˜ao de c´odigos LT cl´assicos: a distribui¸c˜ao
S´oliton Ideal e a distribui¸c˜ao S´oliton Robusta. A distribui¸c˜ao de grau usada
para a constru¸c˜ao de c´odigos LT – Distribui¸c˜ao S´oliton Robusta – ´e constru´ıda
de tal forma que o decodificador possa recuperar a mensagem original com
pouco mais que k s´ımbolos codificados, com probabilidade no m´ınimo (1−δ) [6].
2.4.1
Distribui¸c˜ao S´oliton Ideal
A distribui¸c˜ao S´oliton Ideal ρ(d) ´e definida como:
ρ(d) =
1
k
, para d = 1
1
d(d−1)
, para d = 2, 3, ..., k.
(2-2)
A Figura 2.4 ilustra a distribui¸c˜ao S´oliton Ideal para uma situa¸c˜ao em que
k = 10
4
.
2.4.2
Distribui¸c˜ao S´oliton Robusta
A distribui¸c˜ao S´oliton Robusta µ(d), associada `a vari´avel aleat´oria d que
corresponde ao n´umero de s´ımbolos de entrada conectados a um dado s´ımbolo
de sa´ıda, ´e definida como segue.
µ(d) =
ρ(d) + τ(d)
β
, para 1 ≤ d ≤ k (2-3)
onde β =
k
d=1
(ρ(d) + τ(d)) ´e uma constante de normaliza¸c˜ao.
Cap´ıtulo 2. C´odigos LT 31
0 10 20 30 40 50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
grau d
Probabilidade
ρ(d)
Figura 2.4: A distribui¸c˜ao S´oliton Ideal ρ(d) para o caso k = 10000.
A fun¸c˜ao positiva τ(d) ´e dada por
τ(d) =
¯
R
dk
, para 1 ≤ d ≤
k
¯
R
− 1,
¯
R
k
ln
¯
R
δ
, para d =
k
¯
R
,
0, para d =
k
¯
R
+ 1, ..., k.
(2-4)
Para uma constante apropriada c > 0, o parˆametro
¯
R representa o n´umero
m´edio de s´ımbolos codificados de grau um e ´e definido como
¯
R = c
√
k ln
k
δ
. (2-5)
A Figura 2.5 ilustra a fun¸c˜ao τ(d) para uma situa¸c˜ao em que k = 10
4
,
c = 0.2 e δ = 0.1.
Luby mostrou que, para um valor de c apropriadamente escolhido (in-
dependente de k e δ), o decodificador pode recuperar a mensagem original a
partir de n = kβ = k + c
√
k ln
2
(k/δ) s´ımbolos codificados, com probabilidade
de falha menor que δ [6].
O n´umero de s´ımbolos codificados ´e ajustado em n = kβ. Isto implica
que k (ρ(i) + τ (i)) ´e o valor esperado do n´umero de s´ımbolos codificados de
grau i.
Cap´ıtulo 2. C´odigos LT 32
0 10 20 30 40 50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
grau d
Probabilidade
ρ(d)
τ (d)
Figura 2.5: A distribui¸c˜ao S´oliton Ideal ρ(d) e a fun¸c˜ao positiva τ(d) para o
caso k = 10
4
, c = 0.2 e δ = 0.1.
A Figura 2.6 mostra a distribui¸c˜ao de grau ´otima S´oliton Robusta para
k = 10
4
, c = 0.2 e δ = 0.1. Este valor de c foi escolhido para uma melhor
visualiza¸c˜ao do gr´afico.
0 10 20 30 40 50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
Probabilidade
grau d
µ(d)
Figura 2.6: A distribui¸c˜ao S´oliton Robusta µ(d) para o caso k = 10
4
, c = 0.2
e δ = 0.1.
Cap´ıtulo 2. C´odigos LT 33
2.5
M´etodo das Transforma¸c˜oes Inversas
Esta se¸c˜ao apresenta um m´etodo que vai ser utilizado na implementa¸c˜ao
do codificador e do decodificador LT, mais precisamente na determina¸c˜ao do
grau do s´ımbolo codificado, onde se fazem uso de duas distribui¸c˜oes de proba-
bilidades distintas: a distribui¸c˜ao S´oliton Robusta e a distribui¸c˜ao uniforme.
O m´etodo das transforma¸c˜oes inversas para simular vari´aveis aleat´orias
discretas ´e descrito a seguir:
Para um instante, deseja-se simular uma vari´avel aleat´oria discreta D a
qual pode assumir k valores distintos, com distribui¸c˜ao de probabilidade
P (D = d
j
) = P
j
para j = 1, . . . , k e
j
P
j
= 1.
Ent˜ao, para simular a vari´avel aleat´oria discreta D, considera-se uma
vari´avel aleat´oria uniformemente U distribu´ıda entre (0,1), e faz-se
D =
d
1
, se U < P
1
,
d
2
, se P
1
≤ U < P
1
+ P
2
,
.
.
.
d
j
, se
j−1
i=1
P
i
≤ U <
j
i=1
P
i
,
.
.
.
(2-6)
Como
P (D = d
j
) = P
j−1
i=1
P
i
≤ U <
j
i=1
P
i
= P
j
,
pode-se concluir que D tem a distribui¸c˜ao de probabilidade desejada.
2.5.1
Determina¸c˜ao do grau do s´ımbolo codificado
Usando o m´etodo das transforma¸c˜oes inversas, ´e feita a determina¸c˜ao do
grau (n´umero de vizinhos) dos s´ımbolos codificados a partir de um n´umero
uniformemente distribu´ıdo entre 0 e 1. Basta adotar d
j
= j, onde j determina
o grau do s´ımbolo codificado e P
j
= µ(j).
Cap´ıtulo 2. C´odigos LT 34
De acordo com a codifica¸c˜ao de c´odigos LT, o primeiro passo consiste na
determina¸c˜ao do grau do s´ımbolo a ser codificado. Portanto, utiliza-se o m´etodo
das transforma¸c˜oes inversas para simular a distribui¸c˜ao S´oliton Robusta µ(d),
armazenando para cada s´ımbolo codificado um n´umero U uniformemente
distribu´ıdo entre (0,1).
2.6
Escolha dos parˆametros da distribui¸c˜ao S´oliton Robusta
Esta se¸c˜ao apresenta simula¸c˜oes para a escolha dos parˆametros c e δ
da distribui¸c˜ao de graus S´oliton Robusta. Os resultados da otimiza¸c˜ao desses
parˆametros s˜ao verificados comparando-os aos resultados apresentados por
Mackay em [8].
Em todas as simula¸c˜oes, o n´umero de s´ımbolos necess´arios para decodifi-
car com sucesso foi determinado.
´
E fato que o n´umero de s´ımbolos codificados
que deve ser transmitido depende da probabilidade de apagamento do canal,
mas, para estes casos onde os parˆametros da distribui¸c˜ao S´oliton Robusta
v˜ao ser determinados, considera-se um canal sem perdas. As simula¸c˜oes fo-
ram implementadas considerando k = 1000 (n´umero de s´ımbolos de entrada)
e variando os parˆametros c e δ.
2.6.1
Resultados obtidos das simula¸c˜oes
O objetivo destas simula¸c˜oes ´e verificar a influˆencia dos parˆametros da
distribui¸c˜ao de graus S´oliton Robusta e encontrar os parˆametros operacionais
para o estudo do desempenho de c´odigos LT.
Primeiro, o valor operacional para a constante c foi encontrado variando
tal valor, com uma probabilidade de falha constante de δ = 0.1. Os resultados
destas simula¸c˜oes s˜ao mostrados na Figura 2.7. Estes s˜ao histogramas do
n´umero de s´ımbolos codificados que s˜ao necess´arios para decodificar a men-
sagem original com sucesso. Cada um dos histogramas mostrados foi obtido
ap´os 300 simula¸c˜oes para cada par de c e δ.
De acordo com os histogramas mostrados na Figura 2.7, na Tabela
2.2 encontra-se indicado o n´umero m´edio de s´ımbolos necess´arios para uma
decodifica¸c˜ao bem sucedida. Portanto, com estes resultados obtidos, ´e claro que
um valor operacional para a constante c ´e 0.03, j´a que com esse valor consegue-
Cap´ıtulo 2. C´odigos LT 35
se em m´edia um menor n´umero de s´ımbolos necess´arios para a decodifica¸c˜ao e
uma boa distribui¸c˜ao de tais valores.
1200 1300 1400 1500 1600
0
50
100
c = 0.2
1100 1200 1300 1400
0
50
100
150
c = 0.1
1000 1100 1200 1300 1400
0
50
100
150
c = 0.05
1000 1100 1200 1300 1400
0
50
100
150
c = 0.03
1000 1200 1400 1600 1800
0
50
100
150
c = 0.01
1000 1500 2000 2500
0
50
100
150
c = 0.005
Figura 2.7: Histograma do n´umero de s´ımbolos codificados necess´arios para a
decodifica¸c˜ao com sucesso para distintos valores de c (k = 1000, δ = 0.1).
Tabela 2.2: N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de c (k = 1000, δ = 0.1).
δ = 0.1
c 0.2 0.1 0.05 0.03 0.01 0.005
m´edia 1394 1240 1164 1140 1176 1255
Em seguida, com este valor operacional de c = 0.03 encontrado novas si-
mula¸c˜oes foram realizadas para encontrar o valor operacional de δ. O resultado
de tal procedimento ´e mostrado na Figura 2.8 e na Tabela 2.3 onde encontra-se
indicado o n´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem sucedida
para distintos valores de δ quando c = 0.03. Pode-se observar que, para valores
de δ igual a 0.5, 0.3, 0.2 e 0.1, o n´umero m´edio de s´ımbolos necess´arios para
a decodifica¸c˜ao ´e quase o mesmo. Portanto, ´e poss´ıvel usar quaisquer desses
valores de δ anteriormente mencionados.
´
E importante observar e comentar
Cap´ıtulo 2. C´odigos LT 36
que `a an´alise probabil´ıstica para determinar δ como limitante superior da
probabilidade de falha na decodifica¸c˜ao ´e muito pessimista, j´a que a probabi-
lidade de falha real, geralmente, ´e muito menor que δ [6,15]. Por isso, c´odigos
LT podem ser projetados com grandes valores de δ e ainda apresentam bom
desempenho. Destas simula¸c˜oes, pode-se tamb´em observar que o parˆametro c
tem uma influˆencia muito maior no desempenho e a obten¸c˜ao operacional de
c ´e importante.
1000 1100 1200 1300 1400
0
50
100
150
δ = 0.5
1000 1100 1200 1300 1400
0
50
100
150
δ = 0.3
1000 1200 1400 1600
0
50
100
150
δ = 0.2
1000 1100 1200 1300 1400
0
50
100
δ = 0.1
1000 1100 1200 1300 1400
0
50
100
δ = 0.01
1100 1200 1300 1400 1500
0
50
100
δ = 0.001
Figura 2.8: Histograma do n´umero de s´ımbolos codificados necess´arios para a
decodifica¸c˜ao com sucesso para distintos valores de δ (k = 1000, c = 0.03).
Tabela 2.3: N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de δ (k = 1000, c = 0.03).
c = 0.03
δ 0.5 0.3 0.2 0.1 0.01 0.001
m´edia 1129 1130 1133 1137 1173 1215
Ao longo da disserta¸c˜ao, pacotes de tamanho k = 1000 ser˜ao usados
e os c´odigos LT utilizados far˜ao uso da distribui¸c˜ao S´oliton Robusta com
parˆametros c e δ iguais a 0.03 e 0.1 respectivamente, tendo em vista que se
Cap´ıtulo 2. C´odigos LT 37
verificou, ao longo das simula¸c˜oes anteriores, que estes valores geram bons
c´odigos LT. Considera-se um bom c´odigo LT, aquele que ´e capaz de recuperar
a mensagem original a partir de um n´umero de s´ımbolos de sa´ıda n que ´e um
pouco maior (≈ 10%) que o n´umero de s´ımbolos de entrada k, que formam a
mensagem original (Para valores maiores de k, este percentual ´e menor).
2.7
An´alise de desempenho
Nos c´odigos LT, a probabilidade de sucesso na decodifica¸c˜ao somente ´e
limitada se o n´umero de s´ımbolos de sa´ıda dispon´ıveis ao receptor for limitado.
O que pode ocorrer ´e um maior tempo de espera para a decodifica¸c˜ao completa
da mensagem original (bloco de k s´ımbolos de entrada). Para garantir o sucesso
na decodifica¸c˜ao, pelo menos n = kβ s´ımbolos codificados devem ser recebidos.
Nesta se¸c˜ao ´e analisado o desempenho de c´odigos LT constru´ıdos com
uma distribui¸c˜ao S´oliton Robusta que como ser´a justificado no Cap´ıtulo 3
´e mais apropriada do que a distribui¸c˜ao S´oliton Ideal. O estudo de c´odigos
LT em canais com apagamento avalia o desempenho deste, tomando-se em
considera¸c˜ao as caracter´ısticas do canal.
2.7.1
Desempenho em canais ideais
´
E analisado aqui o n´umero de s´ımbolos codificados necess´arios para a
decodifica¸c˜ao de c´odigos LT em canais ideais (livres de perturba¸c˜oes). As
simula¸c˜oes foram feitas para diferentes valores de k (n´umero de s´ımbolos
de entrada). Ao longo do processo de decodifica¸c˜ao, caso n˜ao se obtivesse
sucesso, o receptor requisitava mais s´ımbolos de sa´ıda ao transmissor. Tal
procedimento foi realizado com a finalidade de obter uma aproxima¸c˜ao real
do n´umero de s´ımbolos necess´arios `a decodifica¸c˜ao bem sucedida. No caso de
uma implementa¸c˜ao pr´atica, n˜ao existe necessidade de requisitar ao trans-
missor mais s´ımbolos de sa´ıda, o decodificador come¸ca a decodifica¸c˜ao assim
que estima possuir s´ımbolos suficientes para uma decodifica¸c˜ao com sucesso.
Entretanto, s´o deixa de aceitar s´ımbolos de sa´ıda provenientes do transmissor
quando a mensagem original for recuperada, eliminando assim a necessidade
de um canal reverso para requisitar mais s´ımbolos de sa´ıda.
Em [14], aconselha-se que o n´umero de s´ımbolos extra requisitados ao
transmissor (G), quando ocorre uma falha na decodifica¸c˜ao, seja G =
√
k. Nas
simula¸c˜oes aqui realizadas, escolhe-se o valor G = 1 a fim de obter uma maior
Cap´ıtulo 2. C´odigos LT 38
precis˜ao a respeito do n´umero real de s´ımbolos necess´arios `a decodifica¸c˜ao bem
sucedida. Na Tabela 2.4, encontram-se indicados o n´umero m´edio de s´ımbolos
necess´arios `a decodifica¸c˜ao bem sucedida, para cada valor de k em fun¸c˜ao dos
parˆametros c = 0.03 e δ = 0.1.
Tabela 2.4: N´umero m´edio de s´ımbolos necess´arios `a decodifica¸c˜ao bem suce-
dida para distintos valores de k (c = 0.03, δ = 0.1)
c = 0.03 e δ = 0.1
k 100 500 1000 2000 3000
m´edia 137 594 1130 2204 3255
Cada uma das m´edias obtidas foi calculada ap´os 250 simula¸c˜oes para
cada valor de k. O n´umero de simula¸c˜oes foi escolhido de maneira arbitr´aria,
tendo em vista que, o n´umero de s´ımbolos de sa´ıda necess´arios para a recu-
pera¸c˜ao da mensagem original, mostrou-se mais concentrado em torno do
valor m´edio exposto na Tabela 2.4.
Finalmente, na Figura 2.9 mostramos que o desempenho dos c´odigos
LT melhora com o crescimento do tamanho do arquivo original, ou seja, a
rela¸c˜ao entre o n´umero de s´ımbolos de sa´ıda e de entrada (overhead) ´e menor
conforme o n´umero de s´ımbolos de entrada k que formam o arquivo original a
ser transmitido vai aumentando.
0 500 1000 1500 2000 2500 3000
1
1.05
1.1
1.15
1.2
1.25
1.3
1.35
1.4
Simbolos de entrada
(1 + )
Figura 2.9: Desempenho do c´odigo LT em canais ideais.
Cap´ıtulo 2. C´odigos LT 39
2.7.2
Desempenho em canais com apagamento
O estudo do desempenho em canais com apagamento ´e importante, j´a
que, como visto anteriormente, um canal que pode corromper ou perder pacotes
pode ser modelado como um canal com apagamento, quando se trata da
transmiss˜ao de pacotes em uma rede de comunica¸c˜ao. Para isso, assume-se
que c´odigos detetores de erros (usados independentemente dos c´odigos LT) s˜ao
usados para detectar erros em um pacote, conforme ilustrado na Figura 2.10.
Caso um dado pacote contenha erros, o c´odigo detector de erros ´e usado para
identificar o pacote que cont´em erros, tratando os mesmos como apagamentos.
Logo, os apagamentos s˜ao descartados pelo decodificador LT. Assim, tem-se
unicamente duas possibilidades: o pacote ´e recebido completamente sem erros
ou ´e descartado.
✲ ✲
❄
❄
✛✛
Fonte
Usu´ario
Codificador
LT
Decodificador
LT
Codificador
Canal
ruidoso
Decodificador
CDE
s
ˆs
BEC
Figura 2.10: Sistema com c´odigos detetores de erros (CDE) usados em conjunto
com c´odigos LT.
A Figura 2.11 mostra a quantidade de s´ımbolos necess´arios para uma
decodifica¸c˜ao com sucesso, em fun¸c˜ao da probabilidade de apagamento do
canal. Pode-se perceber que, `a medida que a probabilidade de apagamento
cresce, maior ´e a quantidade de s´ımbolos codificados necess´arios para una
decodifica¸c˜ao bem sucedida. Isto ´e, quanto maior ´e a probabilidade de apaga-
mento, menos s´ımbolos de sa´ıda chegam ao decodificador.
´
E poss´ıvel observar
ademais que, para probabilidades de apagamento muito baixas, o n´umero
de s´ımbolos codificados necess´arios para a decodifica¸c˜ao bem sucedida tende
a ser uma constante igual a taxa m´ınima do c´odigo LT em uso, ou seja, o
n´umero m´ınimo de s´ımbolos de sa´ıda necess´arios para a decodifica¸c˜ao. Isso
acontece porque praticamente todos os pacotes enviados s˜ao recebidos pelo
decodificador.
Para o caso considerado neste trabalho, cada s´ımbolo ´e representado
por um bit, ent˜ao o canal reduz-se ao canal bin´ario com apagamento (BEC).
Cap´ıtulo 2. C´odigos LT 40
As simula¸c˜oes foram feitas considerando k = 1000. O valor (1 + )k =
βk representa o n´umero m´edio de s´ımbolos de sa´ıda necess´arios para uma
decodifica¸c˜ao bem sucedida.
10
−4
10
−3
10
−2
10
−1
10
0
1.1
1.15
1.2
1.25
1.3
1.35
1.4
1.45
Probabilidade de apagamento do canal BEC
(1 + )
Figura 2.11: Desempenho do c´odigo LT em canais com apagamento.
2.8
Compara¸c˜ao com c´odigos tradicionais para canais com apagamento
Tipicamente, os c´odigos tradicionais para canais com apagamento s˜ao
c´odigos de bloco com taxa fixa, isto ´e, k s´ımbolos de entrada s˜ao usados
para gerar (n − k) s´ımbolos redundantes para um total de n s´ımbolos codi-
ficados, e a taxa do c´odigo ´e R = k/n. Tˆem-se sugerido o uso de c´odigos
Reed-Solomon [16] e c´odigos Tornado [27] para aplica¸c˜oes de distribui¸c˜ao
de dados de maneira confi´avel onde s˜ao requeridos c´odigos para canais com
apagamento. Entretanto, existem severas limita¸c˜oes para implementar tais
c´odigos, por exemplo k e n s˜ao limitados a valores razoavelmente pequenos ou
s˜ao fixados antes que o processo de codifica¸c˜ao comece, sendo assim, melhor
a utiliza¸c˜ao de c´odigos LT. Entre as principais vantagens dos c´odigos LT em
rela¸c˜ao aos c´odigos tradicionais, destacam-se:
• Tempo de codifica¸c˜ao e decodifica¸c˜ao da ordem de k ln(k/δ).
• Capacidade de gerar um n´umero ilimitado de s´ımbolos codificados.
Cap´ıtulo 2. C´odigos LT 41
• Gera¸c˜ao de s´ımbolos de sa´ıda em tempo real.
• N˜ao ´e necess´ario conhecer a priori a caracter´ıstica do canal.
2.8.1
C´odigos Reed-Solomon
Os c´odigos Reed-Solomon s˜ao os melhores conhecidos como c´odigos
MDS (Maximum Distance Separable). Uma grande vantagem dos c´odigos
Reed-Solomon ´e que, sendo a mensagem original formada por k s´ımbolos
de entrada, quaisquer k dos n s´ımbolos codificados gerados s˜ao suficientes
para recuperar a mensagem original. Por outro lado, a desvantagem destes
c´odigos ´e a limita¸c˜ao a valores pequenos do n´umero de s´ımbolos de entrada
k e n´umero de s´ımbolos de sa´ıda n, devido a considera¸c˜oes pr´aticas como o
tempo de codifica¸c˜ao e decodifica¸c˜ao. No entanto, para estes c´odigos, a ordem
do Corpo de Galois em uso limita o n´umero de s´ımbolos de sa´ıda que podem
ser gerados. Em implementa¸c˜oes pr´aticas, um valor t´ıpico para a ordem do
Corpo de Galois ´e 256, o qual limita n a 256 s´ımbolos.
Essa limita¸c˜ao no n´umero de s´ımbolos que podem ser gerados, fazem
que os c´odigos Reed-Solomon n˜ao sejam apropriados para algumas aplica¸c˜oes
como, por exemplo, distribui¸c˜ao de dados em grande quantidade sobre a
Internet. Para um valor baixo de n, pode acontecer de n˜ao serem recebidos
os k s´ımbolos necess´arios `a decodifica¸c˜ao. Nesse caso, o receptor ter´a que
esperar um outro ciclo de transmiss˜ao, recebendo um alto n´umero de s´ımbolos
duplicados, diminuindo a eficiˆencia.
Na pr´atica, os c´odigos Reed-Solomon s˜ao somente eficientes para valores
pequenos de k e n. Isto deve-se a que, para uma implementa¸c˜ao padr˜ao destes
c´odigos, k(n − k)A/2 opera¸c˜oes por s´ımbolo s˜ao necess´arias para produzir os
n s´ımbolos codificados, onde A ´e o tamanho do corpo finito usado [2] [16].
2.8.2
C´odigos Tornado
Os c´odigos Tornado [26] s˜ao c´odigos de bloco baseados em grafos espar-
sos irregulares. Estes c´odigos podem ser projetados usando um alfabeto de
tamanho arbitr´ario.
A vantagem dos c´odigos Tornado ´e que apresentam tempos de codi-
fica¸c˜ao e decodifica¸c˜ao que variam linearmente com o tamanho do arquivo a
ser codificado [2] [26]. Tais c´odigos se assemelham aos c´odigos LT, j´a que usam
Cap´ıtulo 2. C´odigos LT 42
uma regra similar na decodifica¸c˜ao para recuperar os dados originais, isto ´e,
(1+)k s´ımbolos de sa´ıda devem ser recebidos para garantir uma decodifica¸c˜ao
com sucesso. Algumas das limita¸c˜oes destes c´odigos em rela¸c˜ao aos c´odigos
LT s˜ao:
• Apresenta complexidades em sua estrutura. Os c´odigos Tornado utilizam
uma sequˆencia cascateada de grafos bipartidos entre muitas camadas de
s´ımbolos, onde os s´ımbolos de entrada encontram-se na primeira camada
e os s´ımbolos redundantes encontram-se em cada camada subseq¨uente.
Na pr´atica, ´e requerida a mesma estrutura gr´afica para ambos, codifica-
dor e decodificador, ou uma estrutura gr´afica no codificador que logo ´e co-
municada ao decodificador. No entanto, este pr´e-processamento mostra-
se muito dispendioso na pr´atica, sendo o tamanho da estrutura dos grafos
proporcional ao n´umero de s´ımbolos de sa´ıda n, necessitando-se de dife-
rentes estruturas de grafos para cada tamanho de arquivo. Ao contr´ario,
com o uso de c´odigos de LT, o ´unico pr´e-processamento necess´ario ´e o
c´alculo das distribui¸c˜oes de graus usadas na codifica¸c˜ao.
• Impossibilidade de gerar mais s´ımbolos codificados em tempo real, caso
n˜ao sejam recebidos os (1 + )k s´ımbolos necess´arios na decodifica¸c˜ao, j´a
que k e n s˜ao fixados antes do processo de codifica¸c˜ao. Pelo contr´ario, o
codificador LT pode gerar s´ımbolos em tempo real at´e conseguir que a
decodifica¸c˜ao seja bem sucedida.
• Tem-se que conhecer a priori a caracter´ıstica do canal em uso, j´a que,
assim como os c´odigos Reed-Solomon, os c´odigos Tornado devem ter
uma taxa pr´e-fixada. Assim, o que se faz na pr´atica ´e usar a maior proba-
bilidade de apagamento poss´ıvel para garantir o sucesso na decodifica¸c˜ao.
Os c´odigos Reed-Solomon e Tornado s˜ao c´odigos sistem´aticos, isto ´e,
todos os s´ımbolos de entrada que formam o arquivo original aparecem expli-
citamente no bloco de s´ımbolos da sequˆencia codificada, enquanto que c´odigos
LT em geral s˜ao n˜ao-sistem´aticos [6].
3
Projetando a distribui¸c˜ao de graus para c´odigos LT
Neste cap´ıtulo ´e analisado o processo de constru¸c˜ao de uma boa distri-
bui¸c˜ao de graus para os c´odigos LT. Quando estudamos o processo de codifi-
ca¸c˜ao e decodifica¸c˜ao destes c´odigos, fica clara a necessidade de obter-se uma
distribui¸c˜ao de probabilidades que atinja os dois objetivos primordiais em
rela¸c˜ao ao ripple: conjunto de s´ımbolos de entrada cobertos mas ainda n˜ao
processados.
1. Ao longo de processo de decodifica¸c˜ao o tamanho do ripple deve ser
o menor poss´ıvel para evitar um desperd´ıcio de esfor¸co computacional,
visto que s´ımbolos codificados que s˜ao liberados n˜ao ir˜ao cobrir nenhum
s´ımbolo de entrada ainda n˜ao-processado que se encontra no ripple.
2. O tamanho do ripple deve ser suficientemente grande tal que n˜ao fique
vazio antes da conclus˜ao bem sucedida da decodifica¸c˜ao, ou seja, n˜ao deve
ficar vazio antes que todos os s´ımbolos de entrada estejam devidamente
cobertos. Caso contr´ario, este provocaria uma falha na decodifica¸c˜ao.
Uma caracter´ıstica b´asica requerida de uma boa distribui¸c˜ao de graus ´e permi-
tir que os s´ımbolos do ripple sejam processados na mesma taxa em que outros
s˜ao adicionados ao mesmo. Esta caracter´ıstica originou o nome S´oliton, pois
um S´oliton ´e uma onda que equilibra perfeitamente a dispers˜ao e a refra¸c˜ao.
Al´em desses objetivos, uma boa distribui¸c˜ao de graus deve:
• Requerer, em m´edia, a recep¸c˜ao da menor quantidade de s´ımbolos de
sa´ıda poss´ıvel para garantir o sucesso da decodifica¸c˜ao.
• Utilizar o menor n´umero de opera¸c˜oes XOR para gerar um s´ımbolo de
sa´ıda. Isso ´e obtido mantendo-se baixo o grau m´edio dos s´ımbolos de
sa´ıda.
Uma distribui¸c˜ao de graus que consiga atender os objetivos anteriormente
descritos seria aquela que liberasse somente um s´ımbolo a cada itera¸c˜ao, pois
assim o ripple seria mantido no menor tamanho poss´ıvel (um s´ımbolo) j´a que o
s´ımbolo processado a cada itera¸c˜ao seria imediatamente substitu´ıdo por outro,
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 44
conseguindo assim, manter o ripple com apenas um s´ımbolo ao longo de todo o
processo de decodifica¸c˜ao at´e que a decodifica¸c˜ao seja completada com sucesso.
A seguir ´e descrita a distribui¸c˜ao S´oliton Ideal, a qual foi projetada para atingir
os objetivos mencionados.
3.1
Distribui¸c˜ao S´oliton Ideal
Esta se¸c˜ao apresenta a dedu¸c˜ao da distribui¸c˜ao S´oliton Ideal seguindo
a nota¸c˜ao proposta em [8]. Na primeira itera¸c˜ao (t = 0), que corresponde ao
in´ıcio do processo de decodifica¸c˜ao, seja h
0
(d) o n´umero de s´ımbolos codificados
de grau d. Assim, o valor esperado do n´umero de s´ımbolos codificados de grau d
que tem seu grau reduzido para d − 1 na itera¸c˜ao seguinte ´e
h
0
(d)
d
k
, (3-1)
onde k ´e o n´umero de s´ımbolos de entrada. A express˜ao (3-1) ´e o valor
esperado de uma vari´avel binomial, em que d/k ´e a probabilidade de um dos d
vizinhos ser o s´ımbolo presente no ripple a ser processado na itera¸c˜ao seguinte,
reduzindo a d −1 o grau de todos os s´ımbolos codificados que o tenham como
vizinho. Na t-´esima itera¸c˜ao, quando t dos k s´ımbolos de entrada tiverem sido
recuperados e o n´umero de s´ımbolos codificados de grau d for h
t
(d), o valor
esperado do n´umero de s´ımbolos codificados de grau d que ter˜ao seu grau
reduzido para d − 1 ´e
h
t
(d)
d
k −t
. (3-2)
Lembrar que a cada itera¸c˜ao um s´ımbolo de entrada presente no ripple ´e
processado. Assim, a fim de que o valor esperado do n´umero de s´ımbolos
codificados de grau 1 satisfa¸ca a condi¸c˜ao
h
t
(1) = 1 ∀ t ∈ {0, ..., k − 1}, (3-3)
devemos ter inicialmente h
0
(1) = 1 e h
0
(2) = k/2 e, mais genericamente
h
t
(2) =
k − t
2
. (3-4)
Para deduzir a distribui¸c˜ao S´oliton Ideal, basta observar que na segunda
itera¸c˜ao (t = 1), o n´umero de s´ımbolos de grau 2 ´e o n´umero de s´ımbolos
de grau 3 que tiveram seu grau reduzido para 2, mais o n´umero de s´ımbolos
de grau 2 que n˜ao foram reduzidos a grau 1, ou seja,
h
1
(2) =
3
k
h
0
(3) +
h
0
(2) −
2
k
h
0
(2)
.
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 45
Da mesma forma, na terceira itera¸c˜ao (t = 2), o n´umero de s´ımbolos de grau 2
´e o n´umero de s´ımbolos de grau 3 que tiveram seu grau reduzido para 2, mais
o n´umero de s´ımbolos de grau 2 que n˜ao foram reduzidos a grau 1 na itera¸c˜ao
anterior, ou seja,
h
2
(2) =
3
k − 1
h
1
(3) +
h
1
(2) −
2
k − 1
h
1
(2)
.
Assim, mais geralmente tem-se para t > 0,
h
t
(d) =
d + 1
k −(t −1)
h
t−1
(d + 1) +
h
t−1
(d) −
d
k − (t − 1)
h
t−1
(d)
. (3-5)
Logo, ap´os algumas manipula¸c˜oes na equa¸c˜ao (3-5), chega-se `a seguinte
equa¸c˜ao
h
t
(d + 1) =
k − t
d + 1
h
t+1
(d) − h
t
(d)
+
d
d + 1
h
t
(d). (3-6)
Sendo o interesse da presente dedu¸c˜ao encontrar uma f´ormula geral para
h
0
(d), ´e necess´ario eliminar na equa¸c˜ao (3-6) a dependˆencia entre termos de
itera¸c˜oes distintas, ou seja, eliminar a recursividade. Para este fim, o teorema
apresentado a continua¸c˜ao oferece uma forma mais simples.
Teorema 3.1 O n´umero de s´ımbolos codificados de grau d na t-´esima itera¸c˜ao
que leva `a distribui¸c˜ao de grau ´otima, ou seja, que o tamanho do ripple seja 1
´e:
h
t
(d) =
k − t
d(d − 1)
. (3-7)
A prova desse teorema ´e feita por indu¸c˜ao usando a equa¸c˜ao (3-6).
Detalhes da prova por indu¸c˜ao s˜ao apresentados no Apˆendice A.
Agora, fazendo uso do Teorema 3.1, os valores reais que estamos procu-
rando para h
0
(d) s˜ao
h
0
(d) =
k
d(d − 1)
, ∀ d ∈ {2, ..., k}. (3-8)
A fim de obter a distribui¸c˜ao de probabilidade necess´aria, n´os dividimos
h
0
(d) o n´umero de s´ımbolos codificados de grau d na primeira itera¸c˜ao, pelo
n´umero total de s´ımbolos de entrada k que formam a mensagem original [25],
ou seja, normalizamos os valores h
0
(d) e obtemos
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 46
ρ(1) =
1
k
visto que h
0
(1) = 1,
ρ(d) =
1
d(d − 1)
para d = 2, . . . , k
que nada mais ´e que a distribui¸c˜ao S´oliton Ideal desenvolvida por Luby em [6].
Nas Figuras 3.1 e 3.2 tem-se uma ilustra¸c˜ao da evolu¸c˜ao dos valores de h
t
(d)
ao longo do processo de decodifica¸c˜ao. Os blocos sombreados representam os
s´ımbolos de grau d que s˜ao reduzidos a grau d − 1 a cada itera¸c˜ao. Perceba
que em ambas itera¸c˜oes, apenas um s´ımbolo de grau 2 ´e reduzido a grau 1,
conforme requerido pela distribui¸c˜ao S´oliton Ideal.
✲
✻
✮
h
0
(3).
3
k
=
1
2
✻
❄
h
0
(2).
2
k
= 1
✻
❄
h
0
(4).
4
k
=
1
3
✻
❄
h
0
(d)
d
1 2 3 4
1
1 S´ımbolo
Figura 3.1: Distribui¸c˜ao S´oliton
Ideal: primeira itera¸c˜ao.
✲
✻
✮
h
1
(3).
3
k−1
=
1
2
✻
❄
h
1
(2).
2
k−1
= 1
✻
❄
h
1
(4).
4
k−1
=
1
3
✻
❄
h
1
(d)
d
1 2 3 4
1
1 S´ımbolo
Figura 3.2: Distribui¸c˜ao S´oliton
Ideal: segunda itera¸c˜ao.
A distribui¸c˜ao S´oliton Ideal, apesar de apresentar um comportamento
ideal, mostra-se pouco ´util na pr´atica, j´a que uma pequena mudan¸ca no valor
esperado do n´umero de s´ımbolos no ripple (um s´ımbolo) ao longo do processo
de decodifica¸c˜ao, causa um esvaziamento do mesmo, o que leva a uma falha
na decodifica¸c˜ao. Portanto, a distribui¸c˜ao S´oliton Ideal pode ser modificada
com a finalidade de conseguir uma alta probabilidade de que o ripple n˜ao
se esvazie antes que o processo de decodifica¸c˜ao haja sido completado. Essa
modifica¸c˜ao leva a outra distribui¸c˜ao de probabilidade chamada, distribui¸c˜ao
S´oliton Robusta. A Figura 3.3 ilustra o desempenho com a distribui¸c˜ao S´oliton
Ideal, ou seja, a probabilidade de falha (P
F
) na decodifica¸c˜ao ap´os (1 + )k
s´ımbolos de sa´ıda terem sido recebidos. Neste caso, as simula¸c˜oes foram
realizadas com 1000 blocos de tamanho k = 1000 s´ımbolos de entrada.
3.2
Distribui¸c˜ao S´oliton Robusta
O grande problema com a distribui¸c˜ao S´oliton Ideal ´e que o tamanho
do ripple ´e de apenas um s´ımbolo. Qualquer varia¸c˜ao no tamanho deste
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 47
0.9 1 1.1 1.2 1.3 1.4
10
−3
10
−2
10
−1
10
0
Probabilidade de falha
(1 + )
P
F
− Soliton Ideal
P
F
− Soliton Robusta
Figura 3.3: Desempenho das distribui¸c˜oes S´oliton Robusta com parˆametros
c = 0.03 e δ = 0.1 e S´oliton Ideal.
pode fazer que ele seja esvaziado e o processo de decodifica¸c˜ao falhe. A
distribui¸c˜ao S´oliton Robusta procura corrigir essa falha, fazendo com que o
tamanho do ripple seja grande o suficiente tal que, a cada passo do processo
de decodifica¸c˜ao, a probabilidade de que o ripple esvazie seja bem pequena.
Ao mesmo tempo, a distribui¸c˜ao S´oliton Robusta procura obter o menor
tamanho esperado poss´ıvel para o ripple, a fim de minimizar a redundˆancia
surgida de s´ımbolos codificados liberados cobrindo s´ımbolos de entrada que j´a
se encontrem no referido ripple.
A id´eia aqui ´e projetar uma distribui¸c˜ao que mantenha o valor esperado
para o tamanho do ripple em torno de ln(k/δ)
√
k ao longo do processo de
decodifica¸c˜ao, sendo δ a probabilidade de falha no processo. A escolha desse
valor se d´a devido `a observa¸c˜ao de que o processo de decodifica¸c˜ao (cresci-
mento e diminui¸c˜ao do ripple) se assemelha a um “random walk”; e em um
“random walk” de comprimento k, a probabilidade de que o mesmo se desvie
de sua m´edia por um valor maior que ln(k/δ)
√
k ´e no m´aximo δ [6]. Assim,
δ ´e o limite superior da probabilidade de falha na decodifica¸c˜ao.
Repetindo a an´alise utilizada na dedu¸c˜ao da distribui¸c˜ao S´oliton Ideal,
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 48
por´em com o valor esperado do n´umero de s´ımbolos codificados de grau 1 sendo
agora h
t
(1) = 1 +
¯
R para todo t, em vez de 1. Percebe-se entretanto, que ao
contr´ario da distribui¸c˜ao S´oliton Ideal, o valor esperado do n´umero de s´ımbolos
codificados de grau 2 que devem ter o grau reduzido para a unidade n˜ao mais
vale 1, isso porque dentre os
¯
R s´ımbolos adicionais pode haver repeti¸c˜ao. Assim,
existe uma probabilidade igual a
¯
R/k de que o s´ımbolo processado na itera¸c˜ao
encontre-se entre os
¯
R s´ımbolos j´a presentes no ripple. Ent˜ao, o valor esperado
do n´umero de s´ımbolos codificados de grau 2 que devem ter seu grau reduzido
para 1 vale 1 +
¯
R/k, ou seja,
2
k
h
0
(2) = 1 +
¯
R
k
,
o que implica,
h
0
(2) =
k
2
+
¯
R
2
.
Na t-´esima itera¸c˜ao, quando t s´ımbolos tiverem sido recuperados, tˆem-se
2
k − t
h
t
(2) = 1 +
¯
R
k − t
.
Usando o mesmo procedimento que culminou na obten¸c˜ao da Equa¸c˜ao
(3-8) para a dedu¸c˜ao da distribui¸c˜ao S´oliton Ideal, obt´em-se
h
0
(d) =
k
d(d − 1)
+
¯
R
d
, para d > 1. (3-9)
Logo, dividimos o n´umero de s´ımbolos codificados de grau d na primeira
itera¸c˜ao, h
0
(d), pelo n´umero total de s´ımbolos de entrada k, e obt´em-se
µ
d
=
1
d(d − 1)
+
¯
R
kd
= ρ(d) + τ(d), para d > 1, (3-10)
onde µ
d
´e a probabilidade de um s´ımbolo ter grau d.
A seguir ´e explicado o porquˆe da escolha do incremento τ(d). A raz˜ao
para truncar o segundo termo da Equa¸c˜ao (3-10), τ(d), para d > k/
¯
R, e
substitu´ı-lo pelo incremento τ(k/
¯
R), ´e para assegurar que a complexidade da
decodifica¸c˜ao n˜ao cres¸ca mais que O(k ln(k)) [8].
Perceba que no in´ıcio da decodifica¸c˜ao τ(1) assegura que o tamanho do
ripple seja 1 +
¯
R inicialmente. O incremento final τ(k/
¯
R) assegura que todos
os s´ımbolos de entrada n˜ao cobertos, sejam cobertos quando o n´umero destes
for igual ao tamanho do ripple. Em outras palavras, o incremento final τ(k/
¯
R)
assegura que todos os s´ımbolos de entrada sejam selecionados, ao menos uma
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 49
vez, como vizinhos de um s´ımbolo codificado. Isto ´e similar ao processo de
liberar simultaneamente
¯
R ln(
¯
R/δ) bolas (s´ımbolos codificados) para cobrir
¯
R
urnas (s´ımbolos de entradas)
1
. Assim, o desgaste causado pela libera¸c˜ao de
v´arios s´ımbolos codificados para cobrir cada um destes s´ımbolos de entrada ao
menos uma vez ´e somente uma fra¸c˜ao pequena do n´umero total de s´ımbolos
de entrada k. Ent˜ao, o incremento τ(d) ´e definido como
τ(d) =
¯
R
dk
, para 1 ≤ d ≤
k
¯
R
− 1,
¯
R
k
ln
¯
R
δ
, para d =
k
¯
R
,
0, para d =
k
¯
R
+ 1, ..., k.
Finalmente, normalizando µ
d
obtemos
µ(d) =
ρ(d) + τ(d)
β
,
a distribui¸c˜ao S´oliton Robusta definida anteriormente.
Nas Figuras 3.4 e 3.5 tem-se uma ilustra¸c˜ao do processo de decodifica¸c˜ao
usando a distribui¸c˜ao S´oliton Robusta. A interpreta¸c˜ao ´e a mesma das figuras
S´oliton Ideal. Os blocos escuros representam o valor esperado dos s´ımbolos de
grau d que s˜ao reduzidos a grau d − 1, portanto, para d = 2, 3 e 4 os blocos
escuros valem 1,
1
2
e
1
3
de s´ımbolo respectivamente. Os blocos mais claros
representam os s´ımbolos liberados os quais j´a se encontram no ripple e n˜ao
acrescentam nenhuma informa¸c˜ao ao processo de decodifica¸c˜ao. Eles sempre
tˆem o mesmo valor para uma dada itera¸c˜ao, sendo o valor esperado desses
s´ımbolos igual a
¯
R
(k−t)
, onde t representa a itera¸c˜ao.
3.2.1
An´alise da distribui¸c˜ao S´oliton Robusta
Nesta subse¸c˜ao s˜ao apresentados alguns resultados b´asicos envolvendo a
distribui¸c˜ao S´oliton Robusta. Calcula-se aqui o n´umero de s´ımbolos codificados
e o grau m´edio de um s´ımbolo codificado.
Teorema 3.2 O n´umero de s´ımbolos codificados ´e n = k + O
√
k ln
2
(k/δ)
.
1
A an´alise do processo cl´assico de lan¸car bolas aleatoriamente em um conjunto de urnas
mostra que s˜ao necess´arios k ln(k/δ) bolas para assegurar-se que com probabilidade (1 − δ),
todas as k urnas sejam cobertas, ou seja, possuam no m´ınimo uma bola.
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 50
✲
✻
¯
R
k
✻
❄
h
0
(d)
d
1 2 3 4
1
✻
❄
¯
R + 1
¯
R
✙
h
0
(2).
2
k
= 1 +
¯
R
k
h
0
(3).
3
k
=
1
2
+
¯
R
k
✻
❄
✻
❄
✻
❄
h
0
(4).
4
k
Figura 3.4: Distribui¸c˜ao S´oliton
Robusta: primeira itera¸c˜ao.
✲
✻
¯
R
k−1
✻
❄
h
1
(d)
d
1 2 3 4
1
✻
❄
¯
R + 1
¯
R
✙
✙
❨
❨
h
1
(2).
2
k−1
= 1 +
¯
R
k−1
✻
❄
✻
❄
✻
❄
h
1
(3).
3
k−1
=
1
2
+
¯
R
k−1
h
1
(4).
4
k−1
Figura 3.5: Distribui¸c˜ao S´oliton
Robusta: segunda itera¸c˜ao.
Prova:
n = kβ
= k
i
ρ(i) + τ(i)
= k +
k
¯
R
−1
i=1
¯
R
i
+
¯
R ln
¯
R
δ
≤ k +
¯
R H(k/
¯
R) +
¯
R ln
¯
R
δ
.
Para continuar com a prova do teorema, definimos a fun¸c˜ao H(k) como a
s´erie harmˆonica truncada H(k) =
k
j=1
1
j
. Usando a seguinte aproxima¸c˜ao
H(k) ≈ ln(k), a ´ultima express˜ao ´e equivalente a:
≈ k +
¯
R ln
k
¯
R
+
¯
R ln
¯
R
δ
= k +
√
k ln
2
k
δ
e, finalmente,
n = k + O
√
k ln
2
(k/δ)
.
A fun¸c˜ao O (·) ´e somente uma nota¸c˜ao utilizada para medir a complexi-
dade computacional de um determinado algoritmo.
Teorema 3.3 O grau m´edio de um s´ımbolo codificado ´e
¯
D = O (ln(k/δ)).
Cap´ıtulo 3. Projetando a distribui¸c˜ao de graus para c´odigos LT 51
Prova:
¯
D =
i
i (ρ(i) + τ (i))
β
≤
i
i (ρ(i) + τ(i))
=
k+1
i=2
1
i − 1
+
k
¯
R
−1
i=1
¯
R
k
+ ln
¯
R
δ
≤ H(k) + 1 + ln
¯
R
δ
Como H(k) ≈ ln(k) vem,
¯
D = O (ln(k/δ)) .
Na Figura 3.3 encontra-se ilustrado o desempenho da distribui¸c˜ao S´oliton
Robusta com parˆametros c = 0.03 e δ = 0.1. Encontra-se ilustrada a
probabilidade de falha da decodifica¸c˜ao, P
F
, quando (1 + )k s´ımbolos de
sa´ıda s˜ao recebidos. As simula¸c˜oes mais uma vez foram implementadas para
k = 1000.
4
C´odigos LT Bidimensionais
Neste cap´ıtulo s˜ao apresentadas duas novas distribui¸c˜oes de graus: S´oliton
Robusta Melhorada [24] e S´oliton Robusta Truncada para c´odigos LT sis-
tem´aticos [12], al´em de um esquema bidimensional para os c´odigos LT.
4.1
Distribui¸c˜ao de graus S´oliton Robusta Melhorada
Nesta se¸c˜ao ´e apresentada a distribui¸c˜ao S´oliton Robusta Melhorada
(SRM), definida a partir da distribui¸c˜ao S´oliton Robusta de Luby (SR) que foi
definida e estudada nos cap´ıtulos anteriores. Tee, Nguyen et al. observaram,
em [24], a existˆencia de alguns graus d
i
, os quais tˆem uma probabilidade µ(d
i
)
t˜ao baixa, que o n´umero de s´ımbolos dado pelo produto de µ(d
i
) e k pode ser
menor que 1, indicando a ausˆencia de s´ımbolos codificados com estes graus.
Em alguns casos, a distribui¸c˜ao S´oliton Robusta, pode levar a um prematuro
fracasso na decodifica¸c˜ao e uma conseq¨uente perda de s´ımbolos durante o
processo de decodifica¸c˜ao, a menos que o n´umero de s´ımbolos redundantes
seja elevado. Quando o processo de decodifica¸c˜ao ´e interrompido, devido `a
ausˆencia de s´ımbolos codificados de grau 1, precisamos receber mais s´ımbolos
para a recupera¸c˜ao de todos os s´ımbolos originais.
Em vista disto, a proposta de Tee, Nguyen et al., portanto, ´e melhorar o
comportamento da distribui¸c˜ao S´oliton Robusta no caso em que µ(d
i
) · k < 1,
introduzindo um fator extra:
ν =
i
µ(d
i
) · k (4-1)
com a finalidade de criar uma distribui¸c˜ao de graus mais ben´efica, onde
d
i
representa o termo de grau-i da distribui¸c˜ao, que satisfaz as seguintes
condi¸c˜oes:
1
d(d−1)
+
¯
R
kd
·
k
β
< 1 para 2 ≤ d ≤ (
k
¯
R
− 1),
1
d(d−1)
·
k
β
< 1 para (
k
¯
R
+ 1) ≤ d ≤ k.
(4-2)
Cap´ıtulo 4. C´odigos LT Bidimensionais 53
Logo, determina-se o parˆametro ν que ´e um fator complementar para a
distribui¸c˜ao S´oliton Robusta original, com a ajuda do conjunto de desigualda-
des dada por (4-2), para maximizar a freq¨uˆencia relativa de ter s´ımbolos de
grau 1, ou seja, todos aqueles graus d
i
que satisfazem (4-2) tˆem redefinidas as
suas probabilidades de distribui¸c˜ao a zero e a soma de todas essas probabilida-
des de distribui¸c˜ao s˜ao adicionadas `a distribui¸c˜ao de probabilidade de grau 1.
A distribui¸c˜ao S´oliton Robusta Melhorada ´e mostrada na Figura 4.1.
0 5 10 15 20 25 30 35 40 45 50
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
grau d
Probabilidade
Distrib. Soliton Robusta M elhorada
Figura 4.1: A distribui¸c˜ao S´oliton Robusta Melhorada para o caso k = 10000,
c = 0.2 e δ = 0.1
´
E importante fazer uma compara¸c˜ao entre a distribui¸c˜ao S´oliton Robusta
e a distribui¸c˜ao S´oliton Robusta Melhorada. Conforme mostram os resultados
de simula¸c˜ao, examinados adiante, quando ´e utilizada a distribui¸c˜ao SR de
Luby, aproximadamente 1130 s´ımbolos codificados (overhead ≈ 13%) s˜ao
necess´arios para recuperar o arquivo original formado por k = 1000 s´ımbolos
de entrada. Por outro lado, quando a distribui¸c˜ao SRM de Nguyen ´e uti-
lizada, o n´umero de s´ımbolos necess´arios foi reduzido a uma m´edia de 1105
(overhead ≈ 10.5%).
A seguir, mostramos nas Figuras 4.2 e 4.3 os histogramas normalizados
do n´umero de s´ımbolos necess´arios para a decodifica¸c˜ao com sucesso de um
c´odigo LT, utilizando as distribui¸c˜oes de graus anteriormente mencionadas.
Os resultados desses histogramas foram obtidos ap´os 1000 simula¸c˜oes.
Cap´ıtulo 4. C´odigos LT Bidimensionais 54
1050 1100 1150 1200 1250 1300 1350
0
0.05
0.1
0.15
0.2
0.25
Probabilidade
Numero de simbolos requeridos
Figura 4.2: Histograma do n´umero de s´ımbolos necess´arios para a decodifica¸c˜ao
com sucesso de um c´odigo LT com distribui¸c˜ao S´oliton Robusta Melhorada
(k = 1000, c = 0.03 e δ = 0.1).
1050 1100 1150 1200 1250 1300 1350 1400 1450
0
0.05
0.1
0.15
0.2
0.25
Probabilidade
Numero de simbolos requeridos
Figura 4.3: Histograma do n´umero de s´ımbolos necess´arios para a decodifica¸c˜ao
com sucesso de um c´odigo LT com distribui¸c˜ao S´oliton Robusta (k = 1000,
c = 0.03 e δ = 0.1).
Cap´ıtulo 4. C´odigos LT Bidimensionais 55
Tamb´em foram feitas outras simula¸c˜oes, para comprovar o melhor de-
sempenho da distribui¸c˜ao S´oliton Robusta Melhorada em rela¸c˜ao `a S´oliton
Robusta. O resultado destas simula¸c˜oes ´e mostrado na Figura 4.4, onde foi
calculado a taxa de apagamento de s´ımbolo, ou seja, a probabilidade de um
s´ımbolo de entrada n˜ao ser recuperado ap´os a decodifica¸c˜ao de (1+)k s´ımbolos
de sa´ıda, em fun¸c˜ao da capacidade (1−P
a
) do canal BEC. As simula¸c˜oes foram
realizadas para 1000 blocos de entrada, com comprimento k = 1000 e overhead
= 30%.
0.8 0.85 0.9 0.95 1
10
−5
10
−4
10
−3
10
−2
10
−1
10
0
(1 − P
a
)
T axa de apag. de simbolo
Soliton Robusta
Soliton Robusta M elhorada
Figura 4.4: Desempenho das distribui¸c˜oes S´oliton Robusta e S´oliton Robusta
Melhorada para um c´odigo LT(1000,1300) com parˆametros c = 0.03 e δ = 0.1.
´
E importante mencionar que essa grande diferen¸ca no desempenho entre
as duas distribui¸c˜oes, ´e devido `a quantidade de s´ımbolos de entrada que
consegue-se recuperar quando ocorre uma falha na decodifica¸c˜ao. Por exemplo,
para P
a
= 0.1, quando usamos a distribui¸c˜ao S´oliton Robusta e ´e registrada
uma falha na decodifica¸c˜ao, a m´edia de s´ımbolos de entrada que s˜ao recupera-
dos ´e muito baixa (aproximadamente 12%). Por outro lado, quando ´e usada
a distribui¸c˜ao S´oliton Robusta Melhorada, a m´edia de s´ımbolos de entrada
recuperados ´e maior (aproximadamente 94%).
4.2
Distribui¸c˜ao S´oliton Robusta Truncada para C´odigos LT Sistem´aticos
Na distribui¸c˜ao S´oliton Robusta, h´a duas condi¸c˜oes que devem ser sa-
tisfeitas para conseguir recuperar todos os s´ımbolos de entrada a partir dos
s´ımbolos codificados que s˜ao recebidos pelo decodificador. Primeiramente, o
Cap´ıtulo 4. C´odigos LT Bidimensionais 56
n´umero de s´ımbolos codificados deve satisfazer `a condi¸c˜ao n ≥ k + 2 ln(
¯
R
δ
)
¯
R.
Como segunda condi¸c˜ao, o n´umero de s´ımbolos que possuem o mais alto
grau deve obedecer a d ≥
k
¯
R
[6], [8]. Nguyen et al. quando desenvolverem
um c´odigo LT sistem´atico em [11], viram que estas condi¸c˜oes continuavam
v´alidas para a decodibilidade de tais c´odigos com taxas maiores que R =
1
2+
,
onde = 2 ln(
¯
R
δ
) ´e o overhead do c´odigo LT original. Entretanto, para taxas
menores que R =
1
2+
, essas condi¸c˜oes n˜ao s˜ao suficientes, j´a que as densidades
de ambas as matrizes, geradora e de paridade, dos c´odigos LT sistem´aticos
s˜ao baixas.
No intuito de aumentar essas densidades, a distribui¸c˜ao de graus usada
para gerar os s´ımbolos de paridade dos c´odigos LT sistem´aticos, denomina-
da distribui¸c˜ao S´oliton Robusta Truncada (SRT), foi redefinida da seguinte
forma [12]:
Ω(d) = µ(d, γ, ν) =
1
β
1
k
+
¯
R
k
+ ν(d)
para d = γ,
γ
β
1
d
(
d
γ
−1
)
+
¯
R
kd
para d = 2γ, 3γ, ··· ,
γ·k
¯
R
− 1,
¯
R
β
k
ln
¯
R
δ
+
1
(
k
¯
R
−1
)
para d =
γ·k
¯
R
,
0 para d >
γ·k
¯
R
e d = 1,
(4-3)
onde k ´e o n´umero total de s´ımbolos de informa¸c˜ao originais,
¯
R ´e o n´umero
de s´ımbolos com um grau espec´ıfico γ, que satisfaz a condi¸c˜ao de [6]
¯
R ≡
c ln
k
δ
√
k. Al´em do mais, ν representa o fator extra que garante a decodibi-
lidade da distribui¸c˜ao SRM, j´a visto na Equa¸c˜ao (4-1). Ainda em referˆencia `a
Equa¸c˜ao (4-3), temos
β
=
d
[(ρ(d) + τ(d)) + ν(γ)],
onde γ ´e um n´umero inteiro maior que 1. Mantendo-se o grau m´aximo em
d
max
=
γ·k
¯
R
, garantimos que os s´ımbolos originais de entrada ser˜ao representa-
dos no grupo de s´ımbolos de paridade codificados do c´odigo LT sistem´atico.
A Figura 4.5 mostra a distribui¸c˜ao SRT, na qual o eixo das abs-
cissas possui um passo de tamanho γ = 6 e um valor m´aximo de
d
max
=
γ·k
¯
R
=
6×10000
230
= 260. Note que, assim como na Figura 4.1, utilizou-se
c = 0.2 para uma melhor visualiza¸c˜ao do gr´afico.
Cap´ıtulo 4. C´odigos LT Bidimensionais 57
0 50 100 150 200 250 300
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
Probabilidade
grau d
Distrib. Soliton Robusta T runcada
Figura 4.5: A distribui¸c˜ao S´oliton Robusta Truncada Ω(d) para o caso
k = 10000, c = 0.2, δ = 0.1 e γ = 6.
A m´edia dos graus dos s´ımbolos sistem´aticos codificados ´e dada pela
seguinte equa¸c˜ao:
¯
D =
d
d · (ρ(d) + τ(d) + ν(d))
β
+ 1 . (4-4)
4.3
Esquema de c´odigos LT bidimensionais
No intuito de melhorar o desempenho dos c´odigos LT, foi desenvolvida a
id´eia de c´odigos LT bidimensionais, onde os s´ımbolos de entrada s˜ao rearran-
jados em forma de uma matriz, como mostra a Figura 4.6.
s1 s2 s3 sksi
sj
s1 s2 s3
si
sk
sj
... ... ...
...
...
...
Reagrupando
Figura 4.6: Reagrupamento bidimensional dos s´ımbolos de entrada s
k
.
Cap´ıtulo 4. C´odigos LT Bidimensionais 58
4.3.1
Codifica¸c˜ao bidimensional
No esquema anterior onde os s´ımbolos de entrada est˜ao rearranjados en
uma matriz, os blocos correspondentes `as linhas da matriz s˜ao codificados usan-
do um c´odigo LT sistem´atico. Por trabalhar horizontalmente, denominamos
este c´odigo de LT horizontal (LT
H
) que introduz um overhead em cada linha.
Em seguida, as colunas da matriz resultante tamb´em s˜ao codificadas usando
um c´odigo LT n˜ao sistem´atico (LT
V
), agora verticalmente. O c´odigo LT
V
,
por sua vez, introduz um overhead em cada coluna. A Figura 4.7 ilustra este
processo.
Código LT
H
Código LTv
Overhead
devido a
LT (Fixo)
H
{
Overhead
devido a
LT (Variável)
v
{
Figura 4.7: Processo de codifica¸c˜ao e decodifica¸c˜ao bidimensional.
Apesar de a Figura 4.7 mostrar que o overhead vertical ´e vari´avel, neste
ponto da codifica¸c˜ao ele tamb´em ´e fixo. Torna-se vari´avel na decodifica¸c˜ao,
quando o decodificador n˜ao consegue recuperar os s´ımbolos de entrada origi-
nais. Uma explica¸c˜ao mais detalhada ´e dada na decodifica¸c˜ao de c´odigos LT
bidimensionais.
4.3.2
Decodifica¸c˜ao bidimensional
A decodifica¸c˜ao bidimensional ´e feita em duas etapas. Primeiro faz-se
uma decodifica¸c˜ao vertical, coluna a coluna de cada bloco de sa´ıda vertical
para tentar recuperar os s´ımbolos codificados da matriz intermedi´aria, sendo
alguns deles apagados devido a que n˜ao foi poss´ıvel sua recupera¸c˜ao. Logo,
Cap´ıtulo 4. C´odigos LT Bidimensionais 59
faz-se uma decodifica¸c˜ao horizontal linha a linha na matriz intermedi´aria para
tentar recuperar os s´ımbolos de entrada que formam a matriz original.
Quando n˜ao consegue-se recuperar todos os s´ımbolos de entrada (a matriz
original), ou seja, quando ocorre uma falha na decodifica¸c˜ao total, o receptor
requer mais s´ımbolos de sa´ıda. Estes s´ımbolos extras s˜ao adicionados a cada
bloco de sa´ıda vertical dependendo onde for necess´ario. Por isso, o overhead
vertical de cada bloco de sa´ıda vertical passa a ser vari´avel (vide Figura 4.7),
sendo necess´ario determinar uma m´edia de tal overhead, para assim calcular o
overhead total do sistema que ´e definido como:
(1 +
T otal
) = (1 +
Horizontal
) · (1 +
V ertical
) (4-5)
Ap´os o requerimento de s´ımbolos adicionais, o decodificador realiza novamente
as decodifica¸c˜oes vertical e horizontal e o processo se repete at´e que todos os
s´ımbolos de entrada sejam recuperados.
4.3.3
Configura¸c˜oes Utilizadas
Neste trabalho, duas configura¸c˜oes do sistema bidimensional dos c´odigos
LT s˜ao utilizadas, conforme a Tabela 4.1.
Tabela 4.1: Configura¸c˜oes Bidimensionais
C´odigos LT Utilizados 2D–TSR 2D–TSRM
Sistem´atico com distribui¸c˜ao SRT LT
H
LT
H
N˜ao-sistem. com distribui¸c˜ao SR LT
V
—
N˜ao-sistem. com distribui¸c˜ao SRM — LT
V
Como pode-se ver na Tabela 4.1, ambas as configura¸c˜oes bidimensionais
apresentam o mesmo c´odigo LT
H
, que ´e um c´odigo LT sistem´atico [12], utili-
zando a distribui¸c˜ao de graus S´oliton Robusta Truncada (SRT). A diferen¸ca
entre elas est´a no c´odigo LT
V
. A Configura¸c˜ao 2D-TSR faz uso, como LT
V
, de
um c´odigo LT convencional (n˜ao-sistem´atico) [6], com a distribui¸c˜ao S´oliton
Robusta (SR). J´a a Configura¸c˜ao 2D-TSRM, utiliza o mesmo c´odigo como
LT
V
, por´em com a distribui¸c˜ao S´oliton Robusta Melhorada (SRM).
4.4
Resultados obtidos
Nesta se¸c˜ao s˜ao apresentados os resultados das simula¸c˜oes realizadas, com
o intuito de avaliar o desempenho dos c´odigos LT bidimensionais. Para isto,
Cap´ıtulo 4. C´odigos LT Bidimensionais 60
foram comparadas as duas configura¸c˜oes bidimensionais com dois esquemas de
codifica¸c˜ao tradicionais (unidimensionais). Para facilitar a leitura das legendas
dos gr´aficos que mostram os resultados obtidos, vamos a considerar a seguinte
nomenclatura:
• 1D–SR: configura¸c˜ao que corresponde `a codifica¸c˜ao com um c´odigo LT
n˜ao-sistem´atico com distribui¸c˜ao S´oliton Robusta.
• 1D–SRM: configura¸c˜ao que corresponde `a codifica¸c˜ao com um c´odigo
LT n˜ao-sistem´atico com distribui¸c˜ao S´oliton Robusta Melhorada.
• 2D–TSR: configura¸c˜ao que corresponde `a codifica¸c˜ao bidimensional com
o c´odigo LT
H
sendo LT sistem´atico com distribui¸c˜ao S´oliton Robusta
Truncada e o c´odigo LT
V
sendo LT n˜ao-sistem´atico com distribui¸c˜ao
S´oliton Robusta.
• 2D–TSRM: configura¸c˜ao que corresponde `a codifica¸c˜ao bidimensional
com o c´odigo LT
H
sendo LT sistem´atico com distribui¸c˜ao S´oliton Robusta
Truncada e o c´odigo LT
V
sendo LT n˜ao-sistem´atico com distribui¸c˜ao
S´oliton Robusta Melhorada.
Todas as simula¸c˜oes foram obtidas para canal BEC, com 1000 blocos de
tamanho k = 1000 s´ımbolos sendo que, nos casos bidimensionais (configura¸c˜oes
2D–TSR e 2D–TSRM), estes 10
6
s´ımbolos de entrada foram agrupados em
uma matriz (1000x1000), conforme a Figura 4.6.
A primeira simula¸c˜ao realizada buscou determinar o overhead () reque-
rido para conseguir uma decodifica¸c˜ao bem sucedida usando a configura¸c˜ao
2D–TSR. A Figura 4.8 mostra o resultado de tal simula¸c˜ao em fun¸c˜ao da
probabilidade (P
a
) de apagamento do canal BEC. Fazendo uma compara¸c˜ao
deste resultado com a configura¸c˜ao 1D–SR, percebe-se que a proposta bi-
dimensional teve um desempenho pior. Por exemplo, observa-se que, com
P
a
= 0.01, a configura¸c˜ao 1D–SR requer ≈ 13%, enquanto a configura¸c˜ao
2D–TSR requer ≈ 18%. Essa diferen¸ca de 5% ´e aproximadamente mantida
ao longo dos demais valores de P
a
.
Logo, comparou-se a configura¸c˜ao 2D–TSRM com os resultados das
duas configura¸c˜oes que foram apresentadas na Figura 4.8. O resultado dessa
compara¸c˜ao ´e mostrado na Figura 4.9. Pode-se perceber que a configura¸c˜ao
2D–TSRM apresenta uma pequena melhora de desempenho em rela¸c˜ao `a
configura¸c˜ao 1D–SR. Por´em, na Figura 4.10, percebe-se que, para altos valores
de P
a
, mais precisamente para P
a
> 0.1, a configura¸c˜ao 2D–TSRM requer
praticamente o mesmo overhead que a configura¸c˜ao 1D–SRM.
Cap´ıtulo 4. C´odigos LT Bidimensionais 61
10
−4
10
−3
10
−2
10
−1
10
0
1.1
1.15
1.2
1.25
1.3
1.35
1.4
1.45
1.5
Probabilidade de apagamento do canal BEC
(1 + )
Config. 2D–TSR
Config. 1D–SR
Figura 4.8: Compara¸c˜ao de desempenho entre as configura¸c˜oes que usam a
distribui¸c˜ao SR. Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1 e γ = 6.
10
−4
10
−3
10
−2
10
−1
10
0
1.1
1.15
1.2
1.25
1.3
1.35
1.4
1.45
1.5
Probabilidade de apagamento do canal BEC
(1 + )
Config. 2D–TSR
Config. 1D–SR
Config. 2D–TSRM
Figura 4.9: Overhead () requerido para uma decodifica¸c˜ao bem sucedida, em
fun¸c˜ao de P
a
. Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1 e γ = 6.
Cap´ıtulo 4. C´odigos LT Bidimensionais 62
10
−4
10
−3
10
−2
10
−1
10
0
1.1
1.15
1.2
1.25
1.3
1.35
Probabilidade de apagamento do canal BEC
(1 + )
Config. 2D–TSRM
Config. 1D–SRM
Figura 4.10: Compara¸c˜ao de desempenho entre as configura¸c˜oes que usam a
distribui¸c˜ao SRM. Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1 e γ = 6.
Vale observar que, nas Figuras 4.8, 4.9 e 4.10, para as configura¸c˜oes
unidimensionais (1D–SR e 1D–SRM) ´e transmitido um overhead = 5%.
Nos casos bidimensionais (configura¸c˜oes 2D–TSR e 2D–TSRM), os overheads
transmitidos inicialmente s˜ao:
H
= 5% e
V
= 5%. Em caso de falha no
processo de decodifica¸c˜ao, o decodificador requisita que mais s´ımbolos sejam
enviados (aumentando o overhead vertical), at´e que a decodifica¸c˜ao tenha
sucesso. Portanto, nas configura¸c˜oes bidimensionais o overhead vertical ´e
vari´avel. O overhead total, isto ´e, o previamente transmitido mais o requerido
pelo decodificador, ´e que esta sendo calculado e mostrado no eixo vertical dos
gr´aficos mencionados anteriormente.
Finalmente, na Figura 4.11 compara-se a taxa de apagamento de s´ımbolo
em fun¸c˜ao da capacidade (1−P
a
) do canal BEC, para as quatro configura¸c˜oes.
Nestas simula¸c˜oes, utilizou-se um overhead fixo
T otal
= 30%. Sendo que, nos
casos bidimensionais, o overhead foi utilizado da seguinte forma:
H
= 5% e
V
= 24% calculado de acordo `a Equa¸c˜ao (4-5), ambos fixos. Ent˜ao, no deco-
dificador, contabilizou-se os s´ımbolos de entrada que n˜ao foram recuperados
ap´os a decodifica¸c˜ao, gerando-se a taxa de apagamento do gr´afico.
Cap´ıtulo 4. C´odigos LT Bidimensionais 63
Al´em disso, pode-se observar na Figura 4.11, que as configura¸c˜oes que
fazem uso da distribui¸c˜ao S´oliton Robusta (1D–SR e 2D–TSR) apresentam
uma alta taxa de apagamento de s´ımbolos, mesmo quando o canal apresenta
boas condi¸c˜oes (baixos valores de P
a
). Por outro lado, as configura¸c˜oes que
usam a distribui¸c˜ao S´oliton Robusta Melhorada (1D–SRM e 2D–TSRM), tˆem
seus desempenhos melhorados `a medida que a qualidade do canal aumenta.
Por exemplo, com P
a
= 0.12, tem-se que a taxa de apagamento de s´ımbolo da
configura¸c˜ao 2D–TSRM ´e de 7 × 10
−2
, enquanto a da configura¸c˜ao 1D–SRM
´e 2 × 10
−3
. Por´em, observa-se que, para P
a
< 0.06, a configura¸c˜ao 2D–TSRM
proposta passa a apresentar desempenho melhor que o esquema convencional
1D–SRM.
0.8 0.85 0.9 0.95 1
10
−6
10
−5
10
−4
10
−3
10
−2
10
−1
10
0
(1 − P
a
)
T axa apag. de simbolo
Config. 2D–TSR
Config. 1D–SR
Config. 2D–TSRM
Config. 1D–SRM
Figura 4.11: Taxa de apagamento de s´ımbolo em fun¸c˜ao da capacidade do canal
(1 − P
a
). Parˆametros utilizados: k = 1000, c = 0.03, δ = 0.1, γ = 6 e = 30%.
A melhora de desempenho do esquema bidimensional 2D–TSRM pro-
posto em rela¸c˜ao ao esquema unidimensional 1D–SRM, mesmo que apenas para
determinada condi¸c˜ao de canal (P
a
< 0.06), mostra que a id´eia do esquema
bidimensional pode ser aperfei¸coada para a obten¸c˜ao de melhores resultados.
5
Conclus˜oes e Sugest˜oes para trabalhos futuros
Neste cap´ıtulo s˜ao apresentadas as conclus˜oes obtidas no desenvolvimento
do presente trabalho, fazendo uma an´alise cr´ıtica dos resultados obtidos.
Indicaremos tamb´em algumas sugest˜oes de trabalho futuro.
5.1
Conclus˜oes
O objetivo desse trabalho foi investigar e realizar um estudo sobre
c´odigos fontanais em canais com apagamento.
No cap´ıtulo 2 foram apresentados os c´odigos LT, onde foram descritos
os processos de codifica¸c˜ao e decodifica¸c˜ao para posteriormente ser analisado
o desempenho desses c´odigos em canais ideais e canais com apagamento.
Foi verificado que o desempenho dos c´odigos LT melhora com o crescimento
do n´umero de s´ımbolos do bloco de informa¸c˜ao (arquivo original), e, que o
overhead exigido para que uma r´eplica dos dados seja recebida ´e maior a
medida que a probabilidade de apagamento de canal BEC cresce.
No cap´ıtulo 3 foi verificado mediante uma an´alise matem´atica em rela¸c˜ao
ao ripple e mediante simula¸c˜oes (onde foi calculada a probabilidade de falha
P
F
na decodifica¸c˜ao em fun¸c˜ao do overhead), a escolha da distribui¸c˜ao de
graus S´oliton Robusta para c´odigos LT.
No cap´ıtulo 4 foi apresentada uma nova distribui¸c˜ao de graus para
c´odigos LT denominada S´oliton Robusta Melhorada, com a qual foram obtidos
melhores resultados de desempenho para canais com apagamentos, sendo
verificado o proposto por Nguyen em [24]. Adicionalmente, foi proposto um
esquema de c´odigos LT Bidimensionais com duas configura¸c˜oes diferentes
(2D-TSR e 2D-TSRM) as quais inicialmente n˜ao apresentaram resultados
satisfat´orios, na an´alise do overhead requerido para que a decodifica¸c˜ao seja
realizada com sucesso, em rela¸c˜ao `as configura¸c˜oes unidimensionais conven-
cionais (1D-SR e 1D-SRM). Logo, observou-se que fixando-se o overhead em
Cap´ıtulo 5. Conclus˜oes e Sugest˜oes para trabalhos futuros 65
= 30%, e computando a taxa de apagamento de s´ımbolo (probabilidade de
um s´ımbolo de entrada n˜ao ser recuperado ap´os a decodifica¸c˜ao de (1 + )k
s´ımbolos de sa´ıda) em fun¸c˜ao da capacidade (1 − P
a
) do canal BEC, a confi-
gura¸c˜ao 2D-TSRM apresentou um melhor desempenho para P
a
< 0.06.
Foi verificado ainda, com os resultados da simula¸c˜ao realizada neste
trabalho e mostrados no Apˆendice B, que o desempenho de c´odigos Raptor ´e
melhor do que o desempenho dos c´odigos LT com distribui¸c˜ao S´oliton Robusta.
Com base nos resultados preliminares de simula¸c˜ao obtidos neste tra-
balho, conjecturamos que os c´odigos LT bidimensionais tˆem desempenho
pr´oximos do desempenho dos c´odigos Raptor.
5.2
Sugest˜oes para trabalhos futuros
A seguir s˜ao propostas algumas sugest˜oes para trabalhos futuros a serem
realizados nesta ´area:
• Pesquisar uma distribui¸c˜ao de graus para c´odigos LT com a finalidade
de conseguir melhores resultados em desempenho.
• Realizar o mesmo estudo apresentado neste trabalho para outros tipos
de canais, tais como canais BSC, AWGN e canais com desvanecimento.
• Realizar um estudo detalhado sobre outro tipo de c´odigos com taxa
vers´atil, como por exemplo c´odigos em tempo real (Online Codes) [13];
Referˆencias Bibliogr´aficas
[1] 3GPP TSG-SA WG4 S4-AHP238. Specification Text for Systematic
Raptor Forward Error Correction. PSM SWG, Sophia Antipolis,
France, Abril 2005.
[2] BYRES, J. W.; LUBY, M.; MITZENMACHER, M. ; REGE, A.. A Digi-
tal Fountain Approach to Reliable Distribution of Bulk Data.
Proceedings of ACM SIGCOMM ’98, p. 56–57, Setembro 1998.
[3] CATALDI, P.; SHATARSKI, M.; GRANGETTO, M. ; MAGLI, E.. Imple-
mentation and performance evaluation of LT and Raptor codes
for multimedia applications. Proceedings of the 2006 International Con-
ference on Intelligent Information Hiding and Multimedia Signal Processing,
p. 263–266, Dezembro 2006.
[4] ELIAS, P.. Coding for two noisy channels. Information Theory, Third
London Symposium, p. 61–76, 1955.
[5] BELTR
˜
AO NETO, HUMBERTO. Estudo de uma classe de c´odigos
sem-taxa para transmiss˜ao de dados em canais com apagamento.
Disserta¸c˜ao de Mestrado, Universidad Federal de Pernambuco, 2007.
[6] LUBY, M.. LT codes. Proc. of the 43rd Annual IEEE Symp. on Foundation
of Comp. Sc., p. 271–280, Novembro 2002.
[7] MA, Y.; YUAN, D. ; ZHANG, H.. Fountain Codes and Applications
to Reliable Wireless Broadcast System. Proceedings of 2006 IEEE
Information Theory Workshop, 2006.
[8] MACKAY, D. J. C.. Information Theory, Inference, and Learning
Algorithms. Cambridge University Press, 2003.
[9] MAYMOUNKOV, P.; MAZIERES, D.. Rateless codes and big down-
loads. In: Proc. of the 2nd International Workshop Peer-to-Peer System,
2003.
[10] MITZENMACHER, M.. Digital Fountains: A Survey and Look
Forward. IEEE Information Theory Workshop, p. 24–29, Outubro 2004.
Referˆencias Bibliogr´aficas 67
[11] NGUYEN, T.; YANG, L. ; HANZO, L.. Systematic Luby Transform
Codes And Their Soft Decoding. 2007 IEEE Workshop on Signal
Processing Systems in Shanghai, p. 67–72, Outubro 2007.
[12] NGUYEN, T.; YANG, L. ; HANZO, L.. An Optimal Degree Distribu-
tion Design And A Conditional Random Integer Generator For
The Systematic Luby Transform Coded Wireless. WCNC, 2008.
[13] MAYMOUNKOV, P.. Online codes. Technical report, NYW, Relat´orio
T´ecnico 2003-833, Novembro 2002.
[14] LUBY, M.. Information additive code generator and decoder for
communication systems. U.S. Patent No. 7,233,264 B2, Junho 19, 2007.
[15] PUDUCHERI, S.; KLIEWER, J. ; FUJA, T.. The Design and Perfor-
mance of Distributed LT codes. IEEE Transactions on Information
Theory, Vol. 53, No 10:pag. 3740–3754, Outubro 2007.
[16] REED, I. S.; SOLOMON, G.. Polynomial Codes Over Certain Finite
Fields. J. Soc. Indust. Appl. Math, Vol. 8:pag. 300–304, 1960.
[17] RICHARDSON, T. J.; URBANKE, R.. The capacity of low-density
parity-check codes under message-passing decoding. IEEE Trans.
Information Theory, vol. 47:pag. 599–618, Fevereiro 2001.
[18] SAMAD, W. A.. Efficient Video on Demand (VoD) Services in
Broadcast Environments. Disserta¸c˜ao de Mestrado, School of Electrical
Engineering, Stockholm - Sweden, Abril 2006.
[19] SASAKI, C.; HASEGAWA, T. ; KOBAYASHI, S.. On Unicast based
Recovery for Multicast Content Distribution considering XOR-
FEC. Asia-Pacific Conference on Communications, Outubro 2005.
[20] SHANNON, C.. A mathematical theory of communications, volumen
27, pag. 379-423 e 623-656. The Bell System Technical Journal, Julho e
Outubro 2004.
[21] SHOKROLLAHI, A.. Raptor codes. IEEE Transactions on Information
Theory, Vol. 52, No 6:pag. 2551–2567, Junho 2006.
[22] SHOKROLLAHI, A.; LUBY, M.. Systematic Encoding and Decoding
of Chain Reaction Codes. U.S. Patent No. 6,909,383, Junho 21, 2005.
[23] TANNER, R. M.. A recursive approach to low-complexity codes.
IEEE Trans. Information Theory, p. 533–547, Setembro 1981.
Referˆencias Bibliogr´aficas 68
[24] TEE, R.; NGUYEN, T.; YANG, L. ; HANZO, L.. Serially Concatenated
Luby Transform Coding And Bit-Interleaved Coded Modulation
Using Iterative Decoding For The Wireless Internet. Proceedings
of VTC 2006 Spring, Melbourne, vol. 138:pag. 177–182, Maio 2006.
[25] TIRROMEN, T.. Optimizing the degree distribution of LT codes.
Disserta¸c˜ao de Mestrado, HELSINKI UNIVERSITY OF TECHNOLOGY,
Mar¸co 2006.
[26] BYRES, J. W.; LUBY, M.; MITZENMACHER, M. ; REGE, A.. A Digital
Fountain Approach to Asynchronous Reliable Multicast. IEEE J.
on Selected Areas in Communications, Special Issue on Network Support for
Multicast Communications, Vol. 20:pag. 1528–1540, Agosto 2002.
[27] LUBY, M.; MITZENMACHER, M. ; SHOKROLLAHI, A.. Efficient Era-
sure Correction Codes. IEEE Trans. on Information Theory, Vol. 47:pag.
569–584, Fevereiro 2001.
[28] LUBY, M.; WATSON, M.; GASIBA, T.; STOCKHAMMER, T. ; XU,
W.. Raptor Codes for Reliable Download Delivery in Wireless
Broadcast Systems. Conference: CCNC’ 2006, Julho 2005.
[29] WICKER, S. B.. Error Control Systems for Digital Communication
and Storage. Prentice Hall, Upper Saddle River, NJ07458 - USA, 1995.
A
Prova do Teorema 3.1
Usamos prova por indu¸c˜ao para d ∈ {2, . . . , k}:
1. Base da indu¸c˜ao: com d = 2 o resultado provinde de (3-4), isto ´e,
h
t
(2) = (k − t)/2
2. Etapa de indu¸c˜ao: nossa hip´otese de indu¸c˜ao ´e que o Teorema 3.1 ´e
verdadeiro para n, ou seja,
h
t
(n) =
k − t
n(n − 1)
Agora vamos provar o caso de n + 1 utilizando (3-6):
h
t
(n + 1) =
k − t
n + 1
(h
t+1
(n) − h
t
(n)) +
n
n + 1
h
t
(n)
=
k − t
n + 1
k − t − 1
n(n − 1)
−
k − t
n(n − 1)
+
n
n + 1
.
k − t
n(n − 1)
= −
k −t
(n + 1)n(n − 1)
+
n(k − t)
(n + 1)n(n − 1)
=
(n − 1)(k − t)
(n + 1)n(n + 1)
=
k − t
n(n + 1)
.
o que ´e igual ao descrito no Teorema 3.1.
Pela indu¸c˜ao da propriedade de n´umeros naturais, o Teorema 3.1 ´e
verdadeiro para todo d ∈ {2, . . . , k}.
B
C´odigos Raptor
C´odigos Raptor foram introduzidos por Shokrollahi em 2003 [21], como
uma extens˜ao dos c´odigos LT. Os c´odigos Raptor s˜ao uma classe de c´odigos
universais, no sentido que para um determinado n´umero de s´ımbolos de entrada
k, e qualquer overhead ε
Raptor
> 0, o c´odigo Raptor pode gerar um n´umero de
s´ımbolos codificados potencialmente ilimitado tal que qualquer subconjunto
de k(1 + ε
Raptor
) s´ımbolos codificados ´e suficiente para recuperar os k s´ımbolos
de entrada originais com alta probabilidade. Cada s´ımbolo codificado ´e gerado
utilizando O (−log ε
Raptor
) opera¸c˜oes, e os s´ımbolos de entrada originais s˜ao re-
cuperados a partir dos k(1+ε
Raptor
) s´ımbolos com O(−k log ε
Raptor
) opera¸c˜oes.
Uma vers˜ao totalmente especificada dos c´odigos Raptor foi recentemente
aprovada em [1], como um meio para difundir dados de maneira eficiente
atrav´es de uma rede broadcast. Os c´odigos Raptor podem ser abordados por
diferentes ˆangulos. Por um lado, eles podem ser vistos como um c´odigo de
bloco sistem´atico especificado por uma matriz geradora, por outro lado a
id´eia de c´odigos fontanais aleat´orios tamb´em ´e inerente. Um c´odigo Raptor,
conforme especificado por MBMS (Multimedia Broadcast/Multicast Services)
´e um c´odigo fontanal sistem´atico gerando n s´ımbolos codificados.
Nas se¸c˜oes seguintes, explicamos com detalhes a estrutura, o processo
de codifica¸c˜ao e decodifica¸c˜ao do c´odigo Raptor. Esta descri¸c˜ao e simbologia
utilizada seguem de modo muito pr´oximo as abordagens apresentadas em
[18, 28].
B.1
C´odigos Raptor n˜ao-sistem´aticos
Os c´odigos Raptor [21] podem ser codificados e decodificados em tempo
que varia linearmente com k e conseguir um desempenho superior aos c´odigos
LT. A novidade ´e a introdu¸c˜ao de uma etapa de pr´e-codifica¸c˜ao externa apli-
cando um c´odigo de bloco sistem´atico de comprimento fixo, por meio da qual
a parte n˜ao sistem´atica da matriz geradora ´e denotada por uma matriz G
P
de
Apˆendice B. C´odigos Raptor 71
dimens˜ao (m × k). Este c´odigo gera L = k + m s´ımbolos pre-codificados com
m denotando o n´umero de s´ımbolos de paridade, como mostrado na Figura B.1.
E
1
E
2
E
3
E
4
E
5
. . .
D
1
D
2
D
3
D
k
. . .
E
n
. . .
G
P
D
P
D
F
E
G
LT
[1,2,...,n]
S´ımbolos fonte
S´ımbolos pr´e-codificados
S´ımbolos codificados
Figura B.1: Etapa de Pr´e-codifica¸c˜ao em c´odigos Raptor.
Seja D o vetor de dimens˜ao (k ×1), que cont´em os k s´ımbolos de entrada
que entram no c´odigo Raptor n˜ao-sistem´atico. Ent˜ao os s´ımbolos de paridade
pre-codificados denotados pelo vetor D
P
s˜ao obtidos como
D
P
= G
P
· D. (B-1)
O conjunto de s´ımbolos pre-codificados, denotado pelo vetor F de di-
mens˜ao (k+m)×1, ´e ent˜ao dado por
D
T
D
T
P
T
. Estes s´ımbolos pr´e-codificados
servem agora como s´ımbolos de entrada para o c´odigo LT interno subseq¨uente
que opera da mesma maneira como um c´odigo LT convencional e mant´em
a propriedade de produzir n s´ımbolos codificados Raptor. Notar, entretanto,
que a distribui¸c˜ao de graus ´e mudada para os c´odigos Raptor. Os s´ımbolos
codificados denotados pelo vetor E
[1:n]
de dimens˜ao (n × 1), s˜ao obtidos por
E
[1:n]
= G
LT
[1,2,··· ,n]
·
D
T
D
T
P
T
, (B-2)
onde a matriz G
LT
[1,2,··· ,n]
de dimens˜ao n × (k + m) ´e a matriz geradora do
c´odigo LT. As Equa¸c˜oes (B-1) e (B-2) podem ser representadas como
A
[1,2,··· ,n]
·
D
D
P
=
0
E
[1:n]
, (B-3)
atrav´es do qual, a matriz A de dimens˜ao (m + n) × (k + m) conhecida como
“matriz de codifica¸c˜ao” ´e definida por
A
[1,2,··· ,n]
G
P
I
m
G
LT
[1,2,··· ,n]
, (B-4)
e I
m
´e a matriz identidade (m ×m). Notar que a matriz de codifica¸c˜ao A n˜ao
representa uma matriz geradora, mas fornece um conjunto de restri¸c˜oes tanto
Apˆendice B. C´odigos Raptor 72
para a etapa de pre-codifica¸c˜ao quanto para o c´odigo LT interno. Do ponto
de vista da codifica¸c˜ao, o codificador Raptor n˜ao-sistem´atico apenas realiza a
etapa adicional de calcular os s´ımbolos pr´e-codificados. Ent˜ao, um conjunto
de n s´ımbolos codificados consecutivos E
[1:n]
´e obtido de acordo com (B-2).
Mais uma vez, assume-se que no decodificador somente um subconjunto
de s´ımbolos codificados esta dispon´ıvel, indicado pelo vetor identificador de
s´ımbolos codificados i = (i
1
, i
2
, . . . , i
r
). A decodifica¸c˜ao de c´odigos Raptor ´e
realizada baseada na matriz de decodifica¸c˜ao A
[i
1
,i
2
,··· ,i
r
]
definida como
A
[i
1
,i
2
,··· ,i
r
]
G
P
I
m
G
LT
[i
1
,i
2
,...,i
r
]
. (B-5)
Similar ao decodificador LT, o processo de decodifica¸c˜ao para c´odigos Raptor
consiste em resolver um sistema de equa¸c˜oes lineares, especificamente
A
[i
1
,i
2
,··· ,i
r
]
· F =
0
T
E
T
i
1
E
T
i
2
··· E
T
i
r
T
, (B-6)
onde 0 ´e um vetor nulo de dimens˜ao (m × 1), e fazendo que os primeiros k
s´ımbolos pr´e-codificados correspondam aos k s´ımbolos fonte
F
[1:k]
= D. (B-7)
´
E importante que a pr´e-codifica¸c˜ao externa, assim como a distribui¸c˜ao de graus
do c´odigo Raptor seja selecionada apropriadamente para obter um bom desem-
penho do c´odigo. Na realidade, para um c´odigo Raptor como especificado em
MBMS [1], a etapa de pr´e-codifica¸c˜ao consiste de dois c´odigos concatenados
em s´erie, atrav´es do qual os pre-c´odigos externo e interno representam c´odigos
tais como LDPC com a estrutura da matriz geradora quase-regular (n´umero
constante de 1s por linha e por coluna).
Al´em disso, ´e interessante notar que a matriz de decodifica¸c˜ao A
[i
1
,i
2
,··· ,i
r
]
´e uma generaliza¸c˜ao da matriz de codifica¸c˜ao como definida em (B-4) porque
os indices n˜ao s˜ao mais consecutivos, mas somente os indices recebidos s˜ao
tomados em conta. Portanto, nos referimos no restante a qualquer matriz
incluindo as restri¸c˜oes do c´odigo de um vetor arbitr´ario i como “code constraint
matrix” e denotada como A
i
.
B.2
Codifica¸c˜ao Raptor sistem´atica.
Apesar de que o c´odigo Raptor n˜ao-sistem´atico tem um excelente desem-
penho, ´e sabido que para muitas aplica¸c˜oes o acesso direto aos dados originais ´e
Apˆendice B. C´odigos Raptor 73
ben´efico, permitindo aos receptores que n˜ao s˜ao capazes de explorar os pacotes
de redundˆancia, participar ainda em uma sess˜ao somente usando os pacotes
de dados que contem os dados originais. C´odigos sistem´aticos podem propor-
cionar esta propriedade j´a que todos os s´ımbolos fonte aparecem nos s´ımbolos
codificados. No entanto, como o c´odigo LT ´e um c´odigo n˜ao-sistem´atico devido
a sua constru¸c˜ao e o c´odigo interno do c´odigo Raptor ´e tamb´em um c´odigo
LT, ambos c´odigos s˜ao inicialmente n˜ao-sistem´aticos. No seguinte, mostramos
brevemente como c´odigos Raptor n˜ao-sistem´aticos podem ser transformados
em um c´odigo sistem´atico [21, 22].
Como j´a foi mencionado, qualquer c´odigo fontanal pode ser visto como
c´odigo em bloco linear regular representado por uma matriz geradora.
´
E
tamb´em conhecido da teoria de codifica¸c˜ao, que as propriedades de um c´odigo
s˜ao determinadas pelas palavras-c´odigo e n˜ao pela regra de codifica¸c˜ao, isto ´e,
o mapeamento de palavras de informa¸c˜ao `as palavras-c´odigo. Conseq¨uente-
mente, para obter um c´odigo sistem´atico, ´e necess´ario encontrar um mapea-
mento apropriado das palavras de informa¸c˜ao `as palavras-c´odigo tais que os pri-
meiros k s´ımbolos da palavra-c´odigo E
i
correspondam aos primeiros s´ımbolos
fonte C
i
, isto ´e
E
i
= C
i
∀ i = 1, . . . , k (B-8)
onde C representa o vetor s´ımbolo fonte, e C
i
o i-´esimo s´ımbolo fonte. Assu-
mir que a matriz geradora de um c´odigo Raptor n˜ao-sistem´atico para os
primeiros k s´ımbolos ´e denotado pela matriz G
k
de dimens˜ao (k × k) tal que
E
[1:k]
= G
k
· D. Ent˜ao, para garantir (B-8) ´e suficiente multiplicar C pela
inversa de G
k
denotada como G
(−1)
k
tal que a matriz geradora total do c´odigo
sistem´atico proporciona a matriz identidade para as k primeiras posi¸c˜oes.
´
E obvio, que esta propriedade pode ser satisfeita se G
k
tem inversa, qual ´e
equivalente ao caso que a matriz tem posto completo (full rank) k.
A Figura B.2 mostra a estrutura de um c´odigo Raptor sistem´atico, qual
pode ser representada por uma concatena¸c˜ao serial de G
(−1)
k
, o pr´e-c´odigo G
P
,
e a matriz geradora G
LT
do c´odigo LT . Aproveitando o fato que E
[1:k]
= C,
isto ´e, a Equa¸c˜ao (B-8), e as Equa¸c˜oes (B-1) e (B-2), obtemos
G
k
= G
LT
[1,...,k]
·
I
k
G
P
. (B-9)
Uma vez calculada esta matriz, os s´ımbolos fonte podem ser facilmente
mapeados em s´ımbolos intermedi´arios D como D = G
(−1)
k
·C.
Apˆendice B. C´odigos Raptor 74
✻
✲
✻
✲✲
✲
✲✲
✲
✲
Codificador
LT
G
(−1)
k
G
P
RG(i)
C
D
F
D
P
E
i
LT
N˜ao Sistem´atico
Sistem´atico
Raptor
Raptor
Ψ
i
{i, E
i
}
i
Figura B.2: Diagrama em bloco da codifica¸c˜ao Raptor sistem´atica.
B.3
Constru¸c˜ao de codificador e decodificador Raptor sistem´atico
Uma implementa¸c˜ao direta seria construir uma matriz G
k
invert´ıvel e
aplicar a codifica¸c˜ao Raptor n˜ao-sistem´atica como mostrado na Figura B.2.
No entanto, este processo de construir G
k
e calcular sua inversa G
(−1)
k
, pode
ser muito ineficiente do ponto de vista computacional, ent˜ao um procedimento
de codifica¸c˜ao diferente foi proposto em [1].
´
E sugerido que a codifica¸c˜ao pode
ser feita usando uma “code constraint matrix” espec´ıfica, ou seja, a matriz
de codifica¸c˜ao conforme definida em (B-4) para n = k, isto ´e, A
[1,··· ,n=k]
.
Desta forma, os s´ımbolos intermedi´arios D n˜ao necessitam ser calculados
explicitamente, e os s´ımbolos pr´e-codificados F s˜ao obtidos logo por
A
[1,··· ,k]
· F ≡
0
T
C
T
T
. (B-10)
Notar que os s´ımbolos intermedi´arios D s˜ao obtidos inerentemente a
partir de F, como pode ser visto em (B-7). Notar tamb´em que as restri¸c˜oes
em (B-10) s˜ao equivalentes ao processo de decodifica¸c˜ao Raptor conforme
introduzido em (B-3). Os s´ımbolos resultantes D podem agora ser utilizados
como s´ımbolos de entrada para o c´odigo Raptor n˜ao-sistem´atico. As restri¸c˜oes
impostas pela Equa¸c˜ao (B-10) est˜ao representados na Figura B.3, onde (B-8)
foi tomado em conta.
G
P
G
LT
[1,2,··· ,k]
m
k
m
k
.
F
0
E
[1:k]
m
k
L
Figura B.3: Restri¸c˜oes na codifica¸c˜ao do c´odigo Raptor sistem´atico.
Apˆendice B. C´odigos Raptor 75
B.4
Implementa¸c˜ao dos c´odigos Raptor n˜ao-sistem´aticos
Nesta se¸c˜ao vamos descrever como foi realizada a implementa¸c˜ao do
c´odigo Raptor n˜ao-sistem´atico, qual ´e mostrada mediante um diagrama em
blocos na Figura B.4.
✲ ✲
✛✛
Fonte
Usu´ario
Codificador
LDPC
Decodificador
LDPC
Codificador
LT
Canal
BEC
Decodificador
LT
D F
ˆ
D
ˆ
F
❄
✛
E
ˆ
E
Figura B.4: Diagrama em blocos do c´odigo Raptor.
Os c´odigos Raptor pre-codificam os s´ımbolos fonte utilizando um c´odigo
de bloco de comprimento fixo, e em seguida codificam esses novos s´ımbolos
com um c´odigo LT. Este processo de codifica¸c˜ao do c´odigo Raptor ´e mostrado
graficamente na Figura B.5.
...
D
1
D
2
D
k
D
F
L
F
1
F
2
E
1
E
2
E
3
E
n
F
E
S´ımbolos de entrada
S´ımbolos redundantes
S´ımbolos intermediarios
S´ımbolos de sa´ıda
LDPC
LT
D
3
F
3
...
...
Figura B.5: Processo de codifica¸c˜ao do c´odigo Raptor.
A principal vantagem ´e que, para uma decodifica¸c˜ao correta, j´a n˜ao ´e
necess´ario que a decodifica¸c˜ao LT tenha sucesso para todos os s´ımbolos pr´e-
codificados. Assim, ´e poss´ıvel utilizar uma distribui¸c˜ao de graus mais simples
que n˜ao recupere todos os s´ımbolos pr´e-codificados, mas torna-se mais r´apido
o processo de decodifica¸c˜ao. A principal desvantagem dos c´odigos Raptor ´e
que o overhead total ´e delimitado inferiormente pelo overhead do pr´e-c´odigo [3].
O algoritmo de decodifica¸c˜ao ´e composto de duas etapas. Primeiro o
decodificador LT interno entrega um vetor com os s´ımbolos pr´e-codificados
recuperados. Logo, este vetor ´e processado pelo decodificador LDPC externo,
baseado no algoritmo belief propagation para tentar recuperar os k s´ımbolos de
Apˆendice B. C´odigos Raptor 76
entrada originais. Shokrollahi prop˜oe em [21] uma nova distribui¸c˜ao de graus
que somente depende do overhead e tem um grau m´aximo muito menor que k.
Neste trabalho, esta distribui¸c˜ao ser´a chamada “distribui¸c˜ao de Shokrollahi”
e o novo c´odigo LT como “c´odigo LT enfraquecido” (wLT ).
O overhead total do c´odigo Raptor, ε
Raptor
, depende dos overheads do
pr´e-codificador LDPC e do codificador wLT :
(1 + ε
Raptor
) = (1 + ε
LDP C
) · (1 + ε
wLT
). (B-11)
A partir da equa¸c˜ao anterior, ´e claro que, dado um overhead total como obje-
tivo, existem dois parˆametros para projetar. Como conseq¨uˆencia, ´e importante
selecionar o melhor par (ε
LDP C
, ε
wLT
) para conseguir uma decodifica¸c˜ao efi-
ciente. Shokrollahi [21] sugere ajustar ε
wLT
= 0.5 ε
Raptor
. Ent˜ao, a Equa¸c˜ao
(B-11) ´e reduzida a uma express˜ao que relaciona o overhead total (ε
Raptor
) e o
overhead do pr´e-c´odigo
ε
Raptor
=
2 ε
LDP C
1 − ε
LDP C
(B-12)
B.4.1
Constru¸c˜ao do pr´e-c´odigo LDPC
Aqui primeiro descrevemos de maneira breve os c´odigos LDPC e, logo
explicamos como ´e realizado o processo de pr´e-codifica¸c˜ao do c´odigo Raptor.
Vale mencionar que vamos continuar usando a mesma simbologia que foi
utilizada no in´ıcio deste cap´ıtulo.
Os c´odigos LDPC (do inglˆes, low-density parity-check codes), s˜ao c´odigos
de bloco lineares com matriz de paridade H de dimens˜ao (L − k) ×L, onde L
´e o n´umero de s´ımbolos pr´e-codificados. A caracter´ıstica que define os c´odigos
LDPC ´e o fato de que sua matriz de paridade ´e esparsa, ou seja, o n´umero
de valores n˜ao nulos ´e muito menor que o n´umero total de valores na matriz H.
Quanto `a regularidade, existem dois tipos de c´odigos LDPC: regulares
e irregulares. Em c´odigos regulares, todas as linhas e colunas de H tˆem o
mesmo n´umero de 1s, embora este n´umero possa ser diferente para ambas. Se
o n´umero de 1s muda entre colunas e/ou linhas de H, o c´odigo ´e dito irregular.
As caracter´ısticas dos c´odigos LDPC, s˜ao descritas em termos de seus
grafos de Tanner [23]. Um grafo de Tanner ´e um grafo bipartido que cont´em
dois tipos de n´o: n´os de paridade e n´os de vari´avel. Qualquer c´odigo de bloco
Apˆendice B. C´odigos Raptor 77
c
1
N´os de vari´avel
c
2
c
3
c
4
c
5
c
6
c
7
c
8
f
1
f
2
f
3
f
4
N´os de paridade
Figura B.6: Grafo de Tanner correspondente `a matriz de paridade H de (B-13).
linear bin´ario tem um grafo de Tanner correspondente, o qual ´e constru´ıdo a
partir de sua matriz de paridade H. Cada bit na palavra-c´odigo corresponde
a um n´o de vari´avel, e cada equa¸c˜ao de paridade corresponde a um n´o de
paridade. Um n´o de paridade f
i
´e conectado a um n´o de vari´avel c
j
no grafo de
Tanner se, e somente se, o elemento h
ij
da matriz de paridade H ´e 1. A Figura
B.6 mostra o grafo de Tanner associado a um c´odigo cuja matriz de paridade
´e dada por
H =
0 1 0 1 1 0 0 1
1 1 1 0 0 1 0 0
0 0 1 0 0 1 1 1
1 0 0 1 1 0 1 0
. (B-13)
Em [17], ´e mostrado que o desempenho de c´odigos LDPC ´e determinado pela
chamada “distribui¸c˜ao de densidades”, que s˜ao polinˆomios que prov´em uma
descri¸c˜ao da estrutura do grafo de Tanner. De fato, define-se o grau de um n´o
como o n´umero de ramos conectados a ele. Assim, o grau de um n´o de vari´avel
´e o n´umero de equa¸c˜oes de paridade do qual o bit correspondente faz parte,
enquanto que o grau de um n´o de paridade ´e o n´umero de bits envolvidos
na correspondente equa¸c˜ao de paridade. Seja λ
i
a fra¸c˜ao de ramos que est˜ao
conectados aos n´os de vari´avel de grau i, e seja, ρ
i
a fra¸c˜ao de ramos que est˜ao
conectados aos n´os de paridade de grau i. Ent˜ao,
λ(x) =
i
λ
i
x
i−1
(B-14)
´e a distribui¸c˜ao de graus dos n´os de vari´avel, e
ρ(x) =
i
ρ
i
x
i−1
(B-15)
´e a distribui¸c˜ao de graus dos n´os de paridade.
Para a constru¸c˜ao do c´odigo Raptor n˜ao-sistem´atico, usamos um c´odigo
LDPC regular como pr´e-c´odigo C
L
, onde o peso das colunas (w
c
) e linhas (w
r
)
da matriz de paridade H ´e constante. A taxa R do pr´e-c´odigo C
L
´e dada por
Apˆendice B. C´odigos Raptor 78
R =
1 +
ε
Raptor
2
(1 + ε
Raptor
)
= 1 −
w
c
w
r
. (B-16)
A matriz de paridade H do pr´e-c´odigo tem a seguinte forma
H = (H
1
| H
2
) (B-17)
onde as submatrices H
1
e H
2
s˜ao esparsas. A submatriz H
1
´e uma matriz de
dimens˜ao (L − k) × k e a submatriz H
2
´e uma matriz quadrada de dimens˜ao
(L−k)×(L−k) n˜ao singular, ou seja, que tem matriz inversa H
−1
2
.
´
E necess´ario
utilizar o m´etodo de elimina¸c˜ao Gaussiana, para converter a matriz de paridade
original H em uma matriz de paridade sistem´atica
H
SY S
=
H
−1
2
H
1
| I
L−k
= (P | I
L−k
) (B-18)
onde I
L−k
´e a matriz identidade de dimens˜ao (L−k)×(L−k). Ent˜ao, a matriz
geradora do pr´e-c´odigo G
LDP C
´e uma matriz de dimens˜ao (k × L) que tem a
seguinte forma
G
LDP C
=
I
k
| P
T
. (B-19)
Logo, os L = k + s s´ımbolos pr´e-codificados denotados pelo vetor F s˜ao
gerados da seguinte maneira
F = G
T
LDP C
·D, (B-20)
onde os k primeiros s´ımbolos pr´e-codificados correspondem aos k s´ımbolos de
entrada denotados pelo vetor D.
B.4.2
Constru¸c˜ao do c´odigo LT interno
A constru¸c˜ao do c´odigo wLT ´e realizada de maneira similar `a constru¸c˜ao
do c´odigo LT convencional que foi estudado no cap´ıtulo 2. A ´unica diferen¸ca
´e a distribui¸c˜ao de graus Ω
D
(x) dos s´ımbolos de sa´ıda, a qual ´e muito similar
`a distribui¸c˜ao S´oliton Ideal, mas tem algumas modifica¸c˜oes como ter um grau
m´aximo igual a D + 1 que ´e muito menor que o comprimento dos s´ımbolos de
entrada do codificador wLT , e dar um peso apropriado para os s´ımbolos de
sa´ıda de grau 1.
Seja, ε
Raptor
, o overhead do c´odigo Raptor, um n´umero real maior que
zero. Ent˜ao definimos a distribui¸c˜ao de Shokrollahi como
Ω
D
(x) =
1
µ + 1
µx +
x
2
1 · 2
+
x
3
2 ·3
+ ··· +
x
D
(D − 1) · D
+
x
D+1
D
, (B-21)
Apˆendice B. C´odigos Raptor 79
onde D = 4(1 + ε
Raptor
)/ε
Raptor
e µ = (ε
Rapor
/2) + (ε
Raptor
/2)
2
.
Denotamos `a matriz geradora do c´odigo wLT , como G
LT
de dimens˜ao
(n ×L). Logo, os L s´ımbolos intermedi´arios F s˜ao os s´ımbolos de entrada para
o codificador wLT para obter os n s´ımbolos codificados E como
E = G
LT
·F. (B-22)
B.5
Resultados obtidos das simula¸c˜oes
Nesta se¸c˜ao s˜ao apresentados os resultados das simula¸c˜oes realizadas
para comparar o desempenho entre c´odigos Raptor e c´odigos LT, calculando
a probabilidade de falha na decodifica¸c˜ao e a taxa de apagamento de s´ımbolo.
As primeiras simula¸c˜oes foram feitas para determinar a probabilidade
de falha na decodifica¸c˜ao em fun¸c˜ao do overhead (1 + ) para um canal ideal
(P
a
= 0). Os parˆametros utilizados para cada c´odigo s˜ao:
• C´odigo Raptor: Pr´e-c´odigo LDPC regular com k = 1000 s´ımbolos de
entrada, taxa R = (1 + 0.5 )/(1 + ) e w
c
= 3, e um c´odigo wLT com
overhead ε
wLT
=
2
e distribui¸c˜ao de graus de Shokrollahi. (Simula¸c˜oes
con w
c
= 5 e w
c
= 7 conduziram a resultados pr´oximos aos resultados
obtidos com w
c
= 3.)
• C´odigo LT: k = 1000 s´ımbolos de entrada e distribui¸c˜ao de graus
S´oliton Robusta com parˆametros c = 0.03, δ = 0.1.
O resultado destas simula¸c˜oes ´e mostrado na Figura B.7, onde observa-se
um melhor desempenho do c´odigo Raptor em compara¸c˜ao `a c´odigo LT com
distribui¸c˜ao S´oliton Robusta. Para obter tais resultados foram realizadas 1000
simula¸c˜oes para cada valor de overhead.
Logo, foram realizadas outras simula¸c˜oes, onde foi calculado a taxa de
apagamento de s´ımbolo, ou seja, a probabilidade de um s´ımbolo de entrada
n˜ao ser recuperado ap´os a decodifica¸c˜ao de k(1 + ) s´ımbolos de sa´ıda. As
simula¸c˜oes foram feitas para um canal BEC com P
a
= 0.04 e usando os
mesmos parˆametros das simula¸c˜oes anteriores. A figura B.8 mostra a taxa
de apagamento de s´ımbolo em fun¸c˜ao do overhead para c´odigos LT com
distribui¸c˜ao SR e c´odigos Raptor.
Apˆendice B. C´odigos Raptor 80
1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Probabilidade de falha
(1 + )
Codigo LT − SR
Codigo Raptor
Figura B.7: Probabilidade de falha em fun¸c˜ao do overhead. Canal ideal.
1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4
10
−2
10
−1
10
0
T axa de apag. de simbolo
(1 + )
Codigo LT − SR
Codigo Raptor
Figura B.8: Taxa de apagamento de s´ımbolo em fun¸c˜ao do overhead. Canal
BEC com P
a
= 0, 04
Apˆendice B. C´odigos Raptor 81
Finalmente, observou-se atrav´es das simula¸c˜oes mostradas na Figura B.9
que os c´odigos Raptor apresentaram um desempenho inferior ao desempenho
dos c´odigos LT com distribui¸c˜ao SRM.
1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
(1 + )
Probabilidade de falha
Codigo Raptor
Codigo LT − SRM
Figura B.9: Compara¸c˜ao de desempenho entre c´odigos LT com distribui¸c˜ao
SRM e c´odigos Raptor. Canal Ideal.
Este fato ´e conhecido na literatura, que o desempenho de c´odigos Raptor
constru´ıdos com pr´e-codificador LDPC irregular tenha desempenho melhor que
os c´odigos LT/SRM.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
