# 问题求解4-09 代数编码

分类：Problem Solving， 发布于：2019-04-20 15:24:56， 更新于：2019-04-27 23:27:39。 评论

TJ-AATA Chapt. 8 Algebraic Coding Theory

## 8.1 Error-Detecting and Correcting Codes

Typically, messages consist of binary ** encoder**. The message is transmitted and then decoded.

An ** error** occurs if there is a change in one or more bits in the codeword. A

**is a method that either converts an arbitarily received**

*decoding scheme*## 奇偶校验码

见DC2019-6。

### Maximum-Likelihood Decoding

We will assume that transmission errors are rare, and, that when they do occur, they occur independently in each bit; that is, if ** maximum-likelihood decoding**.

A ** binary-symmetric channel** is a model that consists of a transmitter capable of sending a binary signal, either a 0 or a 1, together with a receiver.

**Theorem 8.7** If a binary

### Block Codes

A code is an ** block code** if the information that is to be coded can be divided into blocks of

*encoding function*

*decoding function*A ** codeword** is any element in the image of

Let ** Hamming distance** or

**,**

*distance***for a code,**

*minimum distance***,**

*weight***Proposition 8.11** Let

$w(\boldsymbol{x}) = d(\boldsymbol{x}, \boldsymbol{0})$ ;$d(\boldsymbol{x}, \boldsymbol{y}) \geqslant 0$ ;$d(\boldsymbol{x}, \boldsymbol{y}) = 0$ exactly when$\boldsymbol{x} = \boldsymbol{y}$ ;$d(\boldsymbol{x}, \boldsymbol{y}) = d(\boldsymbol{y}, \boldsymbol{x})$ ;$d(\boldsymbol{x}, \boldsymbol{y}) \leqslant d(\boldsymbol{x}, \boldsymbol{z}) + d(\boldsymbol{z}, \boldsymbol{y})$ .

**Theorem 8.13** Let

## 8.2 Linear Codes

A ** group code** is a code that is also a subgroup of

**Lemma 8.17** Let

**Theorem 8.18** Let

### Linear Codes

Define the ** inner product** of two binary

Let ** null space** of a matrix

**Theorem 8.21** Let

A code is a ** linear code** if it is determined by the null space of some matrix

## 8.3 Parity-Check and Generator Matrices

Suppose that ** canonical parity-check matrix**. More specifically,

*standard generator matrix*An

**Theorem 8.25** If

In light of the theorem, the first ** information bits** and the last

**.**

*check bits***Theorem 8.26** Suppose that

**Lemma 8.27** Let

**Theorem 8.28** Let

**Proposition 8.30** Let

**Theorem 8.31** Let

**Theorem 8.34** Let

## 8.4 Efficient Decoding

If ** syndrome** of

**Proposition 8.36** Let the

**Theorem 8.37** Let

### Coset Decoding

** Coset** or

**uses the cosets of**

*standard decoding*Suppose that ** coset leader**. Once we have determined a coset leader for rach coset, the decoding process becomes a task of calculating

We can make a table that designates a coset leader corresponding to each syndrome. Such a list is called a ** decoding table**.

**Proposition 8.43** Let