Seção 28

Códigos lineares e correção de erros

> Aplicação algébrica de espaços vetoriais e corpos finitos. Esta seção apresenta o núcleo matemático dos códigos lineares sem transformar o curso em um assunto completo de Teoria da Codificação.

Código linear sobre um campo finito

avançadoviz

Um código linear $C$ de comprimento $n$ sobre $F_{q}$ é um subespaço vetorial

C \leq F_{q}^{n} .

Forma equivalente

dim (C) = k,

Um conjunto de palavras-código fechadas sob adição e multiplicação escalar no corpo finito.

Ver detalhe →

é chamado de código linear $[n, k]_{q}$ .

Matriz geradora

avançadoviz

G \in F_{q}^{k \times n} .

Forma equivalente

c = m G .

Converte uma mensagem de símbolos $k$ em uma palavra-código de símbolos $n$ .

Ver detalhe →

Uma mensagem $m \in F_{q}^{k}$ é codificada por

Matriz de verificação de paridade

avançadoviz

Uma matriz de verificação de paridade $H$ satisfaz, para cada palavra de código $c$

H c^{T} = 0 .

Forma equivalente

H \in F_{q}^{(n - k) \times n} .

Além disso, com convenções compatíveis para $G$ e $H$

G H^{T} = 0.

Define restrições lineares que toda palavra-código válida deve satisfazer.

Ver detalhe →

Síndrome

avançadoviz

s = H r^{T} .

Se $r$ for uma palavra-código válida

s = 0 .

Forma equivalente

s = H e^{T} .

Resume quais restrições de paridade uma palavra recebida falha.

Ver detalhe →

Se $r = c + e$ , então

Distância e peso de Hamming

avançadoviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Forma equivalente

w_{H} (x) = d_{H} (x, 0) .

Conta quantas posições diferem entre duas palavras.

Ver detalhe →

O peso de Hamming é

Distância mínima, detecção e correção

avançadoviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Forma equivalente

d_{m i n} - 1

Forma equivalente

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Para um código linear

d_{m i n} = c \neq = 0 min w_{H} (c) .

A separação entre palavras-código determina a capacidade teórica de detecção e correção.

Ver detalhe →

Um código com distância mínima $d_{m i n}$ pode detectar até

erros e corrigir até

erros no modelo clássico de erro de símbolo.

Taxa de um código linear

avançadoviz

R = \frac{k}{n} .

Fração de símbolos na palavra codificada que representa informações independentes.

Ver detalhe →

Seção 28

Códigos lineares e correção de erros

Código linear sobre um campo finito

avançadoviz

Um código linear $C$ de comprimento $n$ sobre $F_{q}$ é um subespaço vetorial

C \leq F_{q}^{n} .

Forma equivalente

dim (C) = k,

Um conjunto de palavras-código fechadas sob adição e multiplicação escalar no corpo finito.

Ver detalhe →

é chamado de código linear $[n, k]_{q}$ .

Matriz geradora

avançadoviz

G \in F_{q}^{k \times n} .

Forma equivalente

c = m G .

Converte uma mensagem de símbolos $k$ em uma palavra-código de símbolos $n$ .

Ver detalhe →

Uma mensagem $m \in F_{q}^{k}$ é codificada por

Matriz de verificação de paridade

avançadoviz

Uma matriz de verificação de paridade $H$ satisfaz, para cada palavra de código $c$

H c^{T} = 0 .

Forma equivalente

H \in F_{q}^{(n - k) \times n} .

Além disso, com convenções compatíveis para $G$ e $H$

G H^{T} = 0.

Define restrições lineares que toda palavra-código válida deve satisfazer.

Ver detalhe →

Síndrome

avançadoviz

s = H r^{T} .

Se $r$ for uma palavra-código válida

s = 0 .

Forma equivalente

s = H e^{T} .

Resume quais restrições de paridade uma palavra recebida falha.

Ver detalhe →

Se $r = c + e$ , então

Distância e peso de Hamming

avançadoviz

d_{H} (x, y) = ∣ {i : x_{i} \neq = y_{i}} ∣.

Forma equivalente

w_{H} (x) = d_{H} (x, 0) .

Conta quantas posições diferem entre duas palavras.

Ver detalhe →

O peso de Hamming é

Distância mínima, detecção e correção

avançadoviz

d_{m i n} = c_{1} \neq = c_{2} min d_{H} (c_{1}, c_{2}) .

Forma equivalente

d_{m i n} - 1

Forma equivalente

t = ⌊ \frac{d _{m i n} - 1}{2} ⌋

Para um código linear

d_{m i n} = c \neq = 0 min w_{H} (c) .

A separação entre palavras-código determina a capacidade teórica de detecção e correção.

Ver detalhe →

Um código com distância mínima $d_{m i n}$ pode detectar até

erros e corrigir até

erros no modelo clássico de erro de símbolo.

Taxa de um código linear

avançadoviz

R = \frac{k}{n} .

Fração de símbolos na palavra codificada que representa informações independentes.

Ver detalhe →