Линейные коды исправляющие ошибки

Обнаружение и исправление ошибок
1. Общие понятия

Для
защиты полезной информации от помех
необходимо в том или ином виде вводить
избыточность: увеличивать число символов
и время их передачи, повторять целые
сообщения, повышать мощность сигнала
— все это ведет к усложнению и удорожанию
аппаратуры. В качестве исследуемой
модели достаточно рассмотреть канал
связи с помехами, потому что к этому
случаю легко сводятся остальные.
Например, запись на диск можно рассматривать
как передачу данных в канал, а чтение с
диска – как прием данных из канала.

Коды
без избыточности обнаружить, а тем более
исправлять
ошибки не могут.
Количество символов, в которых любые
две комбинации кода отличаются друг от
друга, называется кодовым
расстоянием.

Минимальное
количество символов, в которых все
комбинации кода отличаются друг от
друга, называется минимальным
кодовым расстоянием.
Минимальное кодовое расстояние —
параметр, определяющий помехоустойчивость
кода и заложенную в коде избыточность,
т.е. корректирующие свойства кода.

В
общем случае для обнаружения t
ошибок минимальное кодовое расстояние

d₀
= t
+ 1.

Минимальное
кодовое расстояние, необходимое для
одновременного обнаружения t
и исправления

ошибок,

d₀
= t
+ 
+ 1.,

Для
кодов, только исправляющих 
ошибок,

d₀
= 2
+ 1.

Для
того чтобы определить кодовое расстояние
между двумя комбинациями двоичного
кода, достаточно просуммировать эти
комбинации по модулю 2 и подсчитать
число единиц полученной комбинации.

Для
обнаружения и исправления одиночной
ошибки соотношение между числом
информационных разрядив k
и числом корректирующих разрядов 
должно удовлетворять следующим условиям:

при
этом подразумевается, что общая длина
кодовой комбинации

n
= k + ρ

Для
практических расчетов при определении
числа контрольных разрядов кодов с
минимальным кодовым расстоянием d₀
= 3 удобно
пользоваться выражениями

ρ₁₍₂₎
= [ log₂( n + 1
) ],

если
известна длина полной кодовой комбинации
n,
и

ρ₁₍₂₎ =
[log₂{( k
+ 1 ) + [ log₂(
k + 1) ] } ],

если
при расчетах удобнее исходить из
заданного числа информационных символов
k
.

Для
кодов, обнаруживающих все трехкратные
ошибки (d₀= 4),

ρ₁₍₃₎

1
+ log₂
(
n + 1
),

или

ρ
₁₍₃₎

1 + log₂
[ (
k + 1
) + log₂
(
k + 1
) ].

Для
кодов длиной в n
символов, исправляющих одну или две
ошибки (d₀= 5),

ρ₂ 
log₂
(C_n²+ C_n¹
+ 1).

Для практических
расчетов можно пользоваться выражением:

Для
кодов, исправляющих 3 ошибки (d₀= 7),

Линейные групповые коды

Линейными
называются коды, в которых проверочные
символы представляют собой линейные
комбинации информационных символов.

Для
двоичных кодов в качестве линейной
операции используется сложение по
модулю 2.

Последовательность
нулей и единиц, принадлежащих данному
коду, будем называть кодовым
вектором.

Свойство
линейных кодов:

сумма
(разность) кодовых векторов линейного
кода дает вектор, принадлежащий данному
коду.

Линейные
коды образуют алгебраическую группу
по отношению к операции сложения по
модулю 2. В этом смысле они являются
групповыми
кодами.

Свойство
группового кода:

минимальное кодовое
расстояние между кодовыми векторами
группового кода равно минимальному
весу ненулевых кодовых векторов.

Вес
кодового вектора
(кодовой комбинации) равен числу его
ненулевых компонент.

Расстояние
между двумя кодовыми векторами
равно весу вектора, полученного в
результате сложения исходных векторов
по модулю 2. Таким образом, для данного
группового кода

W_min=d_0.

Групповые
коды удобно задавать матрицами,
размерность которых определяется
параметрами кода k
и .
Число строк матрицы равно k,
число столбцов равно

n
= k + 
:

Коды,
порождаемые этими матрицами, известны
как (n,k)-коды,
соответствующие им матрицы называют
порождающими
(производящими, образующими).

Порождающая
матрица P
может быть представлена двумя матрицами
U_k
и H_
(информационной и проверочной). Число
столбцов матрицы H_
равно ,
число столбцов матрицы U_k
равно k

Теорией
и практикой установлено, что в качестве
матрицы U_k
удобно брать единичную матрицу в
канонической форме

Для
кодов с d₀= 2
производящая матрица P
имеет вид

Во всех комбинациях
кода построенного при помощи такой
матрицы, четное число единиц.

Для
кодов с d₀

3 порождающая
матрица не может быть представлена в
форме, общей для всех кодов с данным
d₀_.Вид матрицы
зависит от конкретных требований к
порождающему коду. Этими требованиями
могут быть либо минимум корректирующих
разрядов, либо максимальная простота
аппаратуры.

Корректирующие
коды с минимальным количеством избыточных
разрядов называют плотно
упакованными
или
совершенными
кодами.

Для
кодов d₀= 3
соотношения n
и k
следующие: (3; 1), (7; 4),
(15; 11), (31; 26), (63; 57)
и так далее.

Строчки
образующей матрицы P
представляют собой k
комбинаций искомого кода. Остальные
комбинации кода строятся при помощи
образующей матрицы по следующему
правилу: корректирующие символы,
предназначенные для обнаружения и
исправления ошибки в информационной
части кода, находятся путем суммирования
по модулю 2 тех строк матрицы H_,
номера которых совпадают с номерами
разрядов, содержащих единицы в кодовом
векторе, представляющем информационную
часть кода. Полученную комбинацию
приписывают справа к информационной
части кода и получают полный вектор
корректирующего кода. Аналогичную
процедуру проделывают со второй, третьей
и последующими информационными кодовыми
комбинациями, пока не будет построен
корректирующий код для передачи всех
символов первичного алфавита.

Алгоритм
образования проверочных символов по
известной информационной части кода
может быть записан следующим образом

или

В процессе
декодирования осуществляются проверки,
идея которых в общем виде может быть
представлена следующим образом

Для
каждой конкретной матрицы существует
своя, одна-единственная система проверок.
Проверки производятся по следующему
правилу : в первую проверку вместе с
проверочным рядом b₁
входят информационные разряды, которые
соответствуют единицам первого столбца
проверочной матрицы H_;
во вторую проверку входит второй
проверочный разряд b₂и информационные
разряды, и т. д. Число проверок равно
числу проверочных разрядов корректирующего
кода .

В
результате осуществления проверок
образуется проверочный
вектор
S₁,
S₂,
…, S_,
который называется синдромом.
Если вес синдрома равен нулю, то принятая
комбинация считается безошибочной.
Если хотя бы один разряд проверочного
вектора содержит единицу, то принятая
комбинация содержит ошибку. Исправление
ошибки производится по виду синдрома,
так как каждому ошибочному разряду
соответствует один единственный
проверочный вектор.

Вид
синдрома для каждой конкретной матрицы
может быть определен при помощи
проверочной матрицы Н’,
которая представляет собой транспонированную
матрицу H_,
дополненной единичной матрицей I_,
число столбцов которой равно число
проверочных разрядов кода

Н’
= H_^ТI_.

Столбцы
такой матрицы представляют собой
значение синдрома для разряда,
соответствующего номеру столбца матрицы
Н’.

Процедура исправления
ошибок в процессе декодирования групповых
кодов сводится к следующему.

Строится
кодовая таблица. В первой строке таблицы
располагаются все кодовые векторы A_i.
В первом столбце второй строки размещается
вектор a₁,
вес которого равен 1.

Остальные
позиции второй строки заполняются
векторами, полученными в результате
суммирования по модулю 2 вектора a₁ с А_i,
расположенным в соответствующем столбце
первой строки. В первом столбце третьей
строки записывается вектор a₂,
вес которого также равен 1, однако , если
вектор a₁
содержит единицу в первом разряде, то
a₂
— во втором. В остальные позиции третьей
строки записывают суммы А_iи a₂.

Аналогично
поступают до тех пор, пока не будут
просуммированы с векторами А_i все векторы
a_j
весом 1, с единицей в каждом из n
разрядов. Затем суммируются по модулю
2 векторы a_j,
весом 2, с последовательным перекрытием
всех возможных разрядов. Вес вектора
a_j
определяет число исправляемых ошибок.
Число векторов a_j
определяется возможным числом
неповторяющихся синдромов и равно 2^-1
(нулевая комбинация говорит об отсутствии
ошибки). Условие неповторяемости синдрома
позволяет по его виду определять
один-единственный соответствующий ему
вектор a_j.
Векторы a_jесть векторы
ошибок, которые могут быть исправлены
данным групповым кодом.

По
виду синдрома принятая комбинация может
быть отнесена к тому или иному смежному
классу, образованному сложением по
модулю 2 кодовой комбинации А_i
с вектором ошибки a_j,
т. е. к определенной строке кодовой
таблицы 3.2.1.

Таблица 3.2.1-
Кодовая таблица групповых кодов

a	A₁	A₂	…	A₍₂^k_-1)
a₁	a₁A₁	a₂A₂	…	a₁A₍₂^k_-1)
a₂	a₂A₁	a₂A₂	…	a₂A₍₂^k_-1)
…	…	…	…	…
a₍₂^_-1)	a₍₂^_—₁₎A₁	a₍₂^_-1)A₂	…	a₍₂^_-1)A₍₂^k_-1)

Принятая
кодовая комбинация A^x_nсравнивается
с векторами, записанными в строке,
соответствующей полученному в результате
проверок синдрому. Истинный код будет
расположен в строке той же колонки
таблицы. Процесс исправления ошибки
заключается в замене на обратное значение
разрядов.

Векторы
a₁,
a₂,
…,a₍₂^_-1)не должны
быть равными ни одному из векторов А₁,
А₂,
…, А₍₂^_-1),
в противном случае в таблице появились
бы нулевые векторы.

Пример.

Построить
кодовую таблицу, при помощи которой
обнаруживаются и исправляются все
одиночные ошибки и некоторые ошибки
кратностью r
+ 1,
в информационной
части кода (11,7), построенного по матрице

Решение.

Используя
таблицу 3.2.1, строим кодовую таблицу
3.2.2 для кодов, построенных по данной
матрице P,
кодовые комбинации строятся путем
добавления к четырехразрядным комбинациям
натурального двоичного кода корректирующих
разрядов по правилу, описанному выше.

Определяем
систему проверок исходя из матрицы H_

Находим
вид синдрома для каждой строки таблицы.
Для этого достаточно произвести проверки
для кодовых комбинаций любого столбца
кодовой таблицы.

Для
нашего примера возьмем столбец A₃.

Таблица 3.2.1 – Пример таблицы
для столбца А₃

№

A₁

1000111

A₂

0100011

A₃

1100100

A₄

0010110

A₅

1010001

A₆

0110101

A₇

1110010

1000000

0100000

0010000

0001000

1100000

1001000

1010000

0000111

1100111

1010111

1001111

0100111

0001111

0010111

1100011

0000011

0110011

0101011

1000011

1101011

1110011

0100100

1000100

1110100

1101100

0000100

0101100

0110100

1010110

0110110

0000110

0011110

1110110

1011110

1000110

0010001

1110001

1000001

1011001

0110001

0011001

0000001

1110101

0010101

0100101

0111101

1010101

1111101

1100101

0110010

1010010

1100010

1111010

0010010

0111010

0100010

№

A₈

0001101

A₉

1001010

A₁₀

0101110

A₁₁

1101001

A₁₂

0011011

A₁₃

1011100

A₁₄

0111000

A₁₅

1111111

1001101

0101101

0011101

0000101

1101101

1000101

1011101

0001010

1101010

1011010

1000010

0101010

0000010

0011010

1101110

0001110

0111110

0100110

1001110

1100110

1111110

0101001

1001001

1111001

1100001

0001001

0100001

0111001

1011011

0111011

0001011

0010011

1111011

1010011

1001011

0011100

1111100

1001100

1010100

0111100

0010100

0001100

1111000

0011000

0101000

0110000

1011000

1110000

1101000

0111111

1011111

1101111

1110111

0011111

0110111

0101111

0
1 0 0 1 0 0
1
0 0 0 1 0 0
1
1 1 0 1 0 0
1
1 0 1 1 0 0
0
0 0 0 1 0 0
0
1 0 1 1 0 0
0
1 1 0 1 0 0

Таким
образом вектору ошибки a₁
соответствует синдром 1 1 1

“ a₂ “ 0
1 1

“ a₃ “ 1
1 0

“ a₄ “ 1
0 1

“ a₅ “ 1
0 0

“ a₆ “ 0
1 0

“ a₇ “ 0
0 1

Предположим,
приняты комбинации 1011001, 1000101, 0001100,
0000001 и 1010001. Производим проверки

Синдром
первой принятой комбинации — 101, значит
вектор ошибки а₄
= 0001000, исправление ошибки производится
заменой символа в четвертом разряде
принятой комбинации на обратный. Истинная
комбинация — А₅,
так как принятая комбинация находится
в шестом столбце таблицы в строке,
соответствующей синдрому 101.

Синдром
второй принятой комбинации — 010, находим
ее в шестой строке (010 соответствует а₆)
и в девятом столбце. Истинная комбинация
А₈
= 0001101, т.е. исправлена двойная ошибка.

Синдром
третьей принятой комбинации — 001
соответствует а₇,
истинная комбинация А₁₃.

Синдром
четвертой из принятых комбинаций — 001
также соответствует а₇,
но принятую комбинацию мы находим в
шестом столбце таблицы , следовательно,
истинная комбинация — А₅.

Синдром шестой
принятой комбинации — 000. Ошибки нет.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

From Wikipedia, the free encyclopedia

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as a hybrid of these two types.^[1] Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).^{[citation needed]}

Linear codes are used in forward error correction and are applied in methods for transmitting symbols (e.g., bits) on a communications channel so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent.^[2] A linear code of length n transmits blocks containing n symbols. For example, the [7,4,3] Hamming code is a linear binary code which represents 4-bit messages using 7-bit codewords. Two distinct codewords differ in at least three bits. As a consequence, up to two errors per codeword can be detected while a single error can be corrected.^[3] This code contains 2⁴=16 codewords.

Definition and parameters[edit]

A linear code of length n and dimension k is a linear subspace C with dimension k of the vector space $mathbb {F} _{q}^{n}$ where $mathbb {F} _{q}$ is the finite field with q elements. Such a code is called a q-ary code. If q = 2 or q = 3, the code is described as a binary code, or a ternary code respectively. The vectors in C are called codewords. The size of a code is the number of codewords and equals q^k.

The weight of a codeword is the number of its elements that are nonzero and the distance between two codewords is the Hamming distance between them, that is, the number of elements in which they differ. The distance d of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length n, dimension k, and distance d is called an [n,k,d] code (or, more precisely, $[n,k,d]_{q}$ code).

We want to give $mathbb {F} _{q}^{n}$ the standard basis because each coordinate represents a «bit» that is transmitted across a «noisy channel» with some small probability of transmission error (a binary symmetric channel). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.

Generator and check matrices[edit]

As a linear subspace of $mathbb {F} _{q}^{n}$ , the entire code C (which may be very large) may be represented as the span of a set of $k$ codewords (known as a basis in linear algebra). These basis codewords are often collated in the rows of a matrix G known as a generating matrix for the code C. When G has the block matrix form ${displaystyle {boldsymbol {G}}=[I_{k}|P]}$ , where $I_{k}$ denotes the $ktimes k$ identity matrix and P is some $ktimes (n-k)$ matrix, then we say G is in standard form.

A matrix H representing a linear function $phi :mathbb {F} _{q}^{n}to mathbb {F} _{q}^{n-k}$ whose kernel is C is called a check matrix of C (or sometimes a parity check matrix). Equivalently, H is a matrix whose null space is C. If C is a code with a generating matrix G in standard form, ${displaystyle {boldsymbol {G}}=[I_{k}|P]}$ , then ${displaystyle {boldsymbol {H}}=[-P^{T}|I_{n-k}]}$ is a check matrix for C. The code generated by H is called the dual code of C. It can be verified that G is a $ktimes n$ matrix, while H is a ${displaystyle (n-k)times n}$ matrix.

Linearity guarantees that the minimum Hamming distance d between a codeword c₀ and any of the other codewords c ≠ c₀ is independent of c₀. This follows from the property that the difference c − c₀ of two codewords in C is also a codeword (i.e., an element of the subspace C), and the property that d(c, c₀) = d(c − c₀, 0). These properties imply that

${displaystyle min _{cin C, cneq c_{0}}d(c,c_{0})=min _{cin C, cneq c_{0}}d(c-c_{0},0)=min _{cin C, cneq 0}d(c,0)=d.}$

In other words, in order to find out the minimum distance between the codewords of a linear code, one would only need to look at the non-zero codewords. The non-zero codeword with the smallest weight has then the minimum distance to the zero codeword, and hence determines the minimum distance of the code.

The distance d of a linear code C also equals the minimum number of linearly dependent columns of the check matrix H.

Proof: Because ${boldsymbol {H}}cdot {boldsymbol {c}}^{T}={boldsymbol {0}}$ , which is equivalent to $sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})={boldsymbol {0}}$ , where ${boldsymbol {H_{i}}}$ is the $i^{th}$ column of ${boldsymbol {H}}$ . Remove those items with $c_{i}=0$ , those ${boldsymbol {H_{i}}}$ with $c_{i}neq 0$ are linearly dependent. Therefore, $d$ is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns ${{boldsymbol {H_{j}}}|jin S}$ where $S$ is the column index set. $sum _{i=1}^{n}(c_{i}cdot {boldsymbol {H_{i}}})=sum _{jin S}(c_{j}cdot {boldsymbol {H_{j}}})+sum _{jnotin S}(c_{j}cdot {boldsymbol {H_{j}}})={boldsymbol {0}}$ . Now consider the vector ${boldsymbol {c'}}$ such that ${displaystyle c_{j}'=0}$ if $jnotin S$ . Note ${boldsymbol {c'}}in C$ because ${boldsymbol {H}}cdot {boldsymbol {c'}}^{T}={boldsymbol {0}}$ . Therefore, we have $dleq wt({boldsymbol {c'}})$ , which is the minimum number of linearly dependent columns in ${boldsymbol {H}}$ . The claimed property is therefore proven.

Example: Hamming codes[edit]

As the first class of linear codes developed for error correction purpose, Hamming codes have been widely used in digital communication systems. For any positive integer $rgeq 2$ , there exists a $[2^{r}-1,2^{r}-r-1,3]_{2}$ Hamming code. Since $d=3$ , this Hamming code can correct a 1-bit error.

Example : The linear block code with the following generator matrix and parity check matrix is a $[7,4,3]_{2}$ Hamming code.

${boldsymbol {G}}={begin{pmatrix}1 0 0 0 1 1 0\0 1 0 0 0 1 1\0 0 1 0 1 1 1\0 0 0 1 1 0 1end{pmatrix}},$ ${boldsymbol {H}}={begin{pmatrix}1 0 1 1 1 0 0\1 1 1 0 0 1 0\0 1 1 1 0 0 1end{pmatrix}}$

Example: Hadamard codes[edit]

Hadamard code is a $[2^{r},r,2^{r-1}]_{2}$ linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the $i^{th}$ column is the bits of the binary representation of integer $i$ , as shown in the following example. Hadamard code has minimum distance $2^{r-1}$ and therefore can correct $2^{{r-2}}-1$ errors.

Example: The linear block code with the following generator matrix is a $[8,3,4]_{2}$ Hadamard code:
${boldsymbol {G}}_{Had}={begin{pmatrix}0 0 0 0 1 1 1 1\0 0 1 1 0 0 1 1\0 1 0 1 0 1 0 1end{pmatrix}}$ .

Hadamard code is a special case of Reed–Muller code. If we take the first column (the all-zero column) out from ${boldsymbol {G}}_{Had}$ , we get $[7,3,4]_{2}$ simplex code, which is the dual code of Hamming code.

Nearest neighbor algorithm[edit]

The parameter d is closely related to the error correcting ability of the code. The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A received vector v in $mathbb {F} _{q}^{n}$ .

Output: A codeword $w$ in $C$ closest to $v$ , if any.

We say that a linear $C$ is $t$ -error correcting if there is at most one codeword in ${displaystyle B_{t}(v)}$ , for each $v$ in $mathbb {F} _{q}^{n}$ .

Popular notation[edit]

Codes in general are often denoted by the letter C, and a code of length n and of rank k (i.e., having k code words in its basis and k rows in its generating matrix) is generally referred to as an (n, k) code. Linear block codes are frequently denoted as [n, k, d] codes, where d refers to the code’s minimum Hamming distance between any two code words.

(The [n, k, d] notation should not be confused with the (n, M, d) notation used to denote a non-linear code of length n, size M (i.e., having M code words), and minimum Hamming distance d.)

Singleton bound[edit]

Lemma (Singleton bound): Every linear [n,k,d] code C satisfies $k+dleq n+1$ .

A code C whose parameters satisfy k+d=n+1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

If C₁ and C₂ are two codes of length n and if there is a permutation p in the symmetric group S_n for which (c₁,…,c_n) in C₁ if and only if (c_p(1),…,c_p(n)) in C₂, then we say C₁ and C₂ are permutation equivalent. In more generality, if there is an $ntimes n$ monomial matrix $Mcolon mathbb {F} _{q}^{n}to mathbb {F} _{q}^{n}$ which sends C₁ isomorphically to C₂ then we say C₁ and C₂ are equivalent.

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

Bonisoli’s theorem[edit]

A code is defined to be equidistant if and only if there exists some constant d such that the distance between any two of the code’s distinct codewords is equal to d.^[4] In 1984 Arrigo Bonisoli determined the structure of linear one-weight codes over finite fields and proved that every equidistant linear code is a sequence of dual Hamming codes.^[5]

Examples[edit]

Some examples of linear codes include:

Repetition codes
Parity codes
Cyclic codes
Hamming codes
Golay code, both the binary and ternary versions
Polynomial codes, of which BCH codes are an example
Reed–Solomon codes
Reed–Muller codes
Goppa codes
Low-density parity-check codes
Expander codes
Multidimensional parity-check codes
Toric codes
Turbo codes

Generalization[edit]

Hamming spaces over non-field alphabets have also been considered, especially over finite rings, most notably Galois rings over Z₄. This gives rise to modules instead of vector spaces and ring-linear codes (identified with submodules) instead of linear codes. The typical metric used in this case the Lee distance. There exist a Gray isometry between $mathbb {Z} _{2}^{2m}$ (i.e. GF(2^2m)) with the Hamming distance and $mathbb {Z} _{4}^{m}$ (also denoted as GR(4,m)) with the Lee distance; its main attraction is that it establishes a correspondence between some «good» codes that are not linear over $mathbb {Z} _{2}^{2m}$ as images of ring-linear codes from $mathbb {Z} _{4}^{m}$ .^[6]^[7]^[8]

More recently,^[when?] some authors have referred to such codes over rings simply as linear codes as well.^[9]

References[edit]

^ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.
^ MacKay, David, J.C. (2003). Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. p. 9. Bibcode:2003itil.book…..M. ISBN 9780521642989. In a linear block code, the extra ${displaystyle N-K}$ bits are linear functions of the original $K$ bits; these extra bits are called parity-check bits
^ Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. pp. 210–211. ISBN 978-0-471-06259-2.
^ Etzion, Tuvi; Raviv, Netanel (2013). «Equidistant codes in the Grassmannian». arXiv:1308.6231 [math.CO].
^ Bonisoli, A. (1984). «Every equidistant linear code is a sequence of dual Hamming codes». Ars Combinatoria. 18: 181–186.
^ Marcus Greferath (2009). «An Introduction to Ring-Linear Coding Theory». In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. ISBN 978-3-540-93806-4.
^ «Encyclopedia of Mathematics». www.encyclopediaofmath.org.
^ J.H. van Lint (1999). Introduction to Coding Theory (3rd ed.). Springer. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.
^ S.T. Dougherty; J.-L. Kim; P. Sole (2015). «Open Problems in Coding Theory». In Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Noncommutative Rings and Their Applications. American Mathematical Soc. p. 80. ISBN 978-1-4704-1032-2.

Bibliography[edit]

J. F. Humphreys; M. Y. Prest (2004). Numbers, Groups and Codes (2nd ed.). Cambridge University Press. ISBN 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

External links[edit]

q-ary code generator program
Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, up to date table of the optimal binary codes, includes non-binary codes.
The database of Z4 codes Online, up to date database of optimal Z4 codes.

Источник

From Wikipedia, the free encyclopedia

Definition and parameters[edit]

Generator and check matrices[edit]

${displaystyle min _{cin C, cneq c_{0}}d(c,c_{0})=min _{cin C, cneq c_{0}}d(c-c_{0},0)=min _{cin C, cneq 0}d(c,0)=d.}$

The distance d of a linear code C also equals the minimum number of linearly dependent columns of the check matrix H.

Example: Hamming codes[edit]

Example : The linear block code with the following generator matrix and parity check matrix is a $[7,4,3]_{2}$ Hamming code.

${boldsymbol {G}}={begin{pmatrix}1 0 0 0 1 1 0\0 1 0 0 0 1 1\0 0 1 0 1 1 1\0 0 0 1 1 0 1end{pmatrix}},$ ${boldsymbol {H}}={begin{pmatrix}1 0 1 1 1 0 0\1 1 1 0 0 1 0\0 1 1 1 0 0 1end{pmatrix}}$

Example: Hadamard codes[edit]

Nearest neighbor algorithm[edit]

The parameter d is closely related to the error correcting ability of the code. The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A received vector v in $mathbb {F} _{q}^{n}$ .

Output: A codeword $w$ in $C$ closest to $v$ , if any.

We say that a linear $C$ is $t$ -error correcting if there is at most one codeword in ${displaystyle B_{t}(v)}$ , for each $v$ in $mathbb {F} _{q}^{n}$ .

Popular notation[edit]

(The [n, k, d] notation should not be confused with the (n, M, d) notation used to denote a non-linear code of length n, size M (i.e., having M code words), and minimum Hamming distance d.)

Singleton bound[edit]

Lemma (Singleton bound): Every linear [n,k,d] code C satisfies $k+dleq n+1$ .

A code C whose parameters satisfy k+d=n+1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

Bonisoli’s theorem[edit]

Examples[edit]

Some examples of linear codes include:

Repetition codes
Parity codes
Cyclic codes
Hamming codes
Golay code, both the binary and ternary versions
Polynomial codes, of which BCH codes are an example
Reed–Solomon codes
Reed–Muller codes
Goppa codes
Low-density parity-check codes
Expander codes
Multidimensional parity-check codes
Toric codes
Turbo codes

Generalization[edit]

More recently,^[when?] some authors have referred to such codes over rings simply as linear codes as well.^[9]

References[edit]

^ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.
^ MacKay, David, J.C. (2003). Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. p. 9. Bibcode:2003itil.book…..M. ISBN 9780521642989. In a linear block code, the extra ${displaystyle N-K}$ bits are linear functions of the original $K$ bits; these extra bits are called parity-check bits
^ Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. pp. 210–211. ISBN 978-0-471-06259-2.
^ Etzion, Tuvi; Raviv, Netanel (2013). «Equidistant codes in the Grassmannian». arXiv:1308.6231 [math.CO].
^ Bonisoli, A. (1984). «Every equidistant linear code is a sequence of dual Hamming codes». Ars Combinatoria. 18: 181–186.
^ Marcus Greferath (2009). «An Introduction to Ring-Linear Coding Theory». In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. ISBN 978-3-540-93806-4.
^ «Encyclopedia of Mathematics». www.encyclopediaofmath.org.
^ J.H. van Lint (1999). Introduction to Coding Theory (3rd ed.). Springer. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.
^ S.T. Dougherty; J.-L. Kim; P. Sole (2015). «Open Problems in Coding Theory». In Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Noncommutative Rings and Their Applications. American Mathematical Soc. p. 80. ISBN 978-1-4704-1032-2.

Bibliography[edit]

J. F. Humphreys; M. Y. Prest (2004). Numbers, Groups and Codes (2nd ed.). Cambridge University Press. ISBN 978-0-511-19420-7. Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

External links[edit]

q-ary code generator program
Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, up to date table of the optimal binary codes, includes non-binary codes.
The database of Z4 codes Online, up to date database of optimal Z4 codes.

Источник

В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.

Основы

В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Контроль целостности данных и исправление ошибок — важные задачи на многих уровнях работы с информацией (в частности, физическом, канальном, транспортном уровнях модели OSI).

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи поврежденных блоков — этот подход применяется в основном на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание поврежденных блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (англ. forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок

Корректирующие коды — коды, служащие для обнаружения или исправления ошибок, возникающих при передаче информации под влиянием помех, а также при её хранении.

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приеме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

С кодами, исправляющими ошибки, тесно связаны коды обнаружения ошибок. В отличие от первых, последние могут только установить факт наличия ошибки в переданных данных, но не исправить её.

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

По способу работы с данными коды, исправляющие ошибки делятся на блоковые, делящие информацию на фрагменты постоянной длины и обрабатывающие каждый из них в отдельности, и сверточные, работающие с данными как с непрерывным потоком.

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной ${displaystyle k}$ бит, которые преобразуются в кодовые слова длиной ${displaystyle n}$ бит. Тогда соответствующий блоковый код обычно обозначают ${displaystyle (n,k)}$ . При этом число ${displaystyle R={frac {k}{n}}}$ называется скоростью кода.

Если исходные ${displaystyle k}$ бит код оставляет неизменными, и добавляет ${displaystyle n-k}$ проверочных, такой код называется систематическим, иначе несистематическим.

Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из ${displaystyle k}$ информационных бит сопоставляется ${displaystyle n}$ бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям:

способность исправлять как можно большее число ошибок,
как можно меньшая избыточность,
простота кодирования и декодирования.

Нетрудно видеть, что приведенные требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач.

Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую легкость кодирования и декодирования.

Линейные пространства

Порождающая матрица

Пусть векторы ${displaystyle {overrightarrow {x_{1}}}=(x_{11},..,x_{1n}),{overrightarrow {x_{2}}}=(x_{21},..,x_{2n}),..,{overrightarrow {x_{k}}}=(x_{k1},..,x_{kn})}$ являются базисом линейного пространства ${displaystyle C}$ . По определению базиса, любой вектор ${displaystyle {overrightarrow {v}}in C}$ можно представить в виде линейной комбинации базисных векторов:
${displaystyle {overrightarrow {v}}={c_{1}}{overrightarrow {x_{1}}}+{c_{2}}{overrightarrow {x_{2}}}+...+{c_{k}}{overrightarrow {x_{k}}}}$ ,
либо в матричной форме, как:

${displaystyle {overrightarrow {v}}=({c_{1}},{c_{2}},..,{c_{k}}){begin{bmatrix}x_{11}&x_{12}&..&x_{1n}\x_{21}&x_{22}&..&x_{2n}\..&..&..&..\x_{k1}&x_{k2}&..&x_{kn}\end{bmatrix}}={overrightarrow {c}}G}$ ,

где
${displaystyle G={begin{bmatrix}x_{11}&x_{12}&..&x_{1n}\x_{21}&x_{22}&..&x_{2n}\..&..&..&..\x_{k1}&x_{k2}&..&x_{kn}\end{bmatrix}}}$
называется порождающей матрицей линейного пространства.

Это соотношение устанавливает связь между векторами коэффициентов ${displaystyle {overrightarrow {c}}=({c_{1}},{c_{2}},..,{c_{k}})}$
и векторами ${displaystyle {overrightarrow {v}}in C}$ . Перечисляя все векторы коэффициентов ${displaystyle {overrightarrow {c}}=({c_{1}},{c_{2}},..,{c_{k}})}$ можно получить все векторы ${displaystyle {overrightarrow {v}}in C}$ . Иными словами, матрица ${displaystyle G}$ порождает линейное пространство.

Проверочная матрица

Другим способом задания линейных пространств является описание через проверочную матрицу.

Пусть ${displaystyle mathbb {C} }$ — линейное k-мерное пространство над полем ${displaystyle mathbb {F} _{q}}$ и ${displaystyle mathbb {W} }$ — ортогональное дополнение ${displaystyle mathbb {C} }$ . Тогда по одной из теорем линейной алгебры, размерность ${displaystyle mathbb {W} }$ равна ${displaystyle r=n-k}$ . Поэтому в ${displaystyle mathbb {W} }$ существует r базисных векторов. Пусть ${displaystyle {overrightarrow {h}}_{1}=({{h_{1}}_{1}},...,{{h_{1}}_{n}}),{overrightarrow {h}}_{2}=({{h_{2}}_{1}},...,{{h_{2}}_{n}}),...,{overrightarrow {h}}_{r}=({{h_{r}}_{1}},...,{{h_{r}}_{n}})}$ базис в ${displaystyle mathbb {W} }$ .

Тогда любой вектор ${displaystyle {overrightarrow {v}}in C}$ удовлетворяет следующей системе линейных уравнений:

${displaystyle {begin{cases}h_{11}x_{1}+h_{12}x_{2}+...+h_{1n}x_{n}=0\h_{21}x_{1}+h_{22}x_{2}+...+h_{2n}x_{n}=0\...\h_{r1}x_{1}+h_{r2}x_{2}+...+h_{rn}x_{n}=0end{cases}}}$

Или в матричной форме:
${displaystyle {overrightarrow {v}}H^{T}=0}$ ,

где ${displaystyle H={begin{bmatrix}{overrightarrow {h}}_{1}\{overrightarrow {h}}_{2}\...\{overrightarrow {h}}_{r}\end{bmatrix}}={begin{bmatrix}h_{11}&h_{12}&..&h_{1n}\h_{21}&h_{22}&..&h_{2n}\..&..&..&..\h_{k1}&h_{k2}&..&h_{kn}\end{bmatrix}}}$
— проверочная матрица.

Приведенную систему линейных уравнений следует рассматривать, как систему проверок для всех векторов линейного пространства, поэтому матрица ${displaystyle mathbb {H} }$ называется проверочной матрицей.

Формальное определение

Линейный код длины n и ранга k является линейным подпространством C размерности k векторного пространства ${displaystyle mathbb {F} _{q}^{n}}$ , где ${displaystyle mathbb {F} _{q}}$ — конечномерное поле из q элементов. Такой код с параметром q называется q-арным кодом (напр. если q = 5 — то это 5-арный код). Если q = 2 или q = 3, то код представляет собой двоичный код, или тернарный соответственно.

Линейный (блоковый) код — такой код, что множество его кодовых слов образует ${displaystyle k}$ -мерное линейное подпространство (назовем его ${displaystyle C}$ ) в ${displaystyle n}$ -мерном линейном пространстве, изоморфное пространству ${displaystyle k}$ -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного ${displaystyle k}$ -битного вектора на невырожденную матрицу ${displaystyle G}$ , называемую порождающей матрицей.

Пусть ${displaystyle C^{perp }}$ — ортогональное подпространство по отношению к ${displaystyle C}$ , а ${displaystyle H}$ — матрица, задающая базис этого подпространства. Тогда для любого вектора ${displaystyle {overrightarrow {v}}in C}$ справедливо:

${displaystyle {overrightarrow {v}}H^{T}={overrightarrow {0}}}$ .

Свойства и важные теоремы

Минимальное расстояние и корректирующая способность

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами ${displaystyle {overrightarrow {v_{1}}}}$ и ${displaystyle {overrightarrow {v_{2}}}}$ называется количество отличных бит на соответствующих позициях, то есть число «единиц» в векторе ${displaystyle {overrightarrow {v_{1}}}oplus {overrightarrow {v_{2}}}}$ .

Минимальное расстояние ${displaystyle d}$ линейного кода является минимальным из всех расстояний Хемминга всех пар кодовых слов.

Вес вектора — ${displaystyle w}$ расстояние Хемминга между этим вектором и нулевым вектором, иными словами — число ненулевых компонент вектора.

Теорема 1:

Минимальное расстояние ${displaystyle d}$ линейного кода равно минимальному из весов Хемминга ненулевых кодовых слов:

${displaystyle d=min _{{overrightarrow {c}}in C,{overrightarrow {c}}not ={overrightarrow {0}}}(w({overrightarrow {c}}))}$

Доказательство:

Расстояние между двумя векторами ${displaystyle d({overrightarrow {x}},{overrightarrow {y}})}$ удовлетворяет равенству ${displaystyle d({overrightarrow {x}},{overrightarrow {y}})=w({overrightarrow {x}}-{overrightarrow {y}})}$ , где ${displaystyle w({overrightarrow {t}})}$ — вес Хемминга вектора ${displaystyle {overrightarrow {t}}}$ . Из того, что разность любых двух кодовых слов линейного кода также является кодовым словом линейного кода, вытекает утверждение теоремы:
${displaystyle d=min _{{overrightarrow {c}}in C,{overrightarrow {c}}not ={overrightarrow {0}}}w({overrightarrow {c}})}$

Минимальное расстояние Хемминга ${displaystyle d}$ является важной характеристикой линейного блокового кода. Она определяет другую, не менее важную характеристику — корректирующую способность:

${displaystyle t=leftlfloor {frac {d-1}{2}}rightrfloor }$ , здесь угловые скобки обозначают округление «вниз».

Корректирующая способность определяет, какое максимальное число ошибок в одном кодовом слове код может гарантированно исправить.

Поясним на примере. Предположим, что есть два кодовых слова A и B, расстояние Хемминга между ними равно 3. Если было передано слово A, и канал внес ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову A, чем B. Но если каналом были внесены ошибки в двух битах, декодер может посчитать, что было передано слово B.

Число обнаруживаемых ошибок — число ошибок, при котором код может судить об ошибочной ситуации. Это число равно

${displaystyle f=d-1}$ .

Теорема 2 (без доказательства):

Если любые ${displaystyle l<=d-1}$ столбцов проверочной матрицы H линейного (n, k)-кода линейно независимы, то минимальное расстояние кода равно по меньшей мере d. Если при этом найдутся d линейно зависимых столбцов, то минимальное расстояние кода равно d в точности.

Теорема 3 (без доказательства):

Если минимальное расстояние линейного (n, k)-кода равно d, то любые ${displaystyle l<=d-1}$ столбцов проверочной матрицы H линейно независимы и найдутся d линейно зависимых столбцов.

Коды Хемминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

${displaystyle {overrightarrow {s}}={overrightarrow {r}}H^{T}}$ , где ${displaystyle {overrightarrow {r}}}$ — принятый вектор,

будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

Код Рида-Малера

Код Рида-Малера [en:Reed-Muller code] — линейный код.

Общий метод кодирования линейных кодов

Линейный код длины n с k информационными символами является k-мерным линейным подпространством, поэтому каждое кодовое слово является линейной комбинацией базисных векторов ${displaystyle {overrightarrow {g_{1}}}=(g_{11},..,g_{1n}),{overrightarrow {g_{2}}}=(g_{21},..,g_{2n}),..,{overrightarrow {g_{k}}}=(g_{k1},..,g_{kn})}$ подпространства:

${displaystyle {overrightarrow {c}}={m_{1}}{overrightarrow {g_{1}}}+{m_{2}}{overrightarrow {g_{2}}}+...+{m_{k}}{overrightarrow {g_{k}}}}$ .

Либо с помощью порождающей матрицы:

${displaystyle {overrightarrow {c}}={overrightarrow {m}}G=({m_{1}},{m_{2}},..,{m_{k}}){begin{bmatrix}g_{11}&g_{12}&..&g_{1n}\g_{21}&g_{22}&..&g_{2n}\..&..&..&..\g_{k1}&g_{k2}&..&g_{kn}\end{bmatrix}}}$ ,
где ${displaystyle {overrightarrow {m}}=({m_{1}},..,{m_{k}}),{m_{1}},..,{m_{k}}in mathbb {Q} }$

Это соотношение есть правило кодирование, по которому информационное слово ${displaystyle {overrightarrow {m}}=({m_{1}},..,{m_{k}})}$ отображается в кодовое ${displaystyle {overrightarrow {c}}=({c_{1}},..,{c_{n}})}$

Общий метод обнаружения ошибок в линейном коде

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова ${displaystyle {overrightarrow {r_{i}}}}$ соответствует наиболее вероятное переданное слово ${displaystyle {overrightarrow {u_{i}}}}$ . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора ${displaystyle {overrightarrow {r_{i}}}}$ вычисляется синдром ${displaystyle {overrightarrow {s_{i}}}={overrightarrow {r_{i}}}H^{T}}$ . Поскольку ${displaystyle {overrightarrow {r_{i}}}={overrightarrow {v_{i}}}+{overrightarrow {e_{i}}}}$ , где ${displaystyle {overrightarrow {v_{i}}}}$ — кодовое слово, а ${displaystyle {overrightarrow {e_{i}}}}$ — вектор ошибки, то ${displaystyle {overrightarrow {s_{i}}}={overrightarrow {e_{i}}}H^{T}}$ . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды

Несмотря на то, что исправление ошибок в линейных кодах уже значительно проще исправления в большинстве нелинейных, для большинства кодов этот процесс все ещё достаточно сложен. Циклические коды, кроме более простого декодирования, обладают и другими важными свойствами.

Циклическим кодом является линейный код, обладающий следующим свойством: если ${displaystyle {overrightarrow {v}}}$ является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово ${displaystyle {overrightarrow {v}}=(v_{0},v_{1},...,v_{n-1})}$ представляется в виде полинома ${displaystyle v(x)=v_{0}+v_{1}x+...+v_{n-1}x^{n-1}}$ . При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на ${displaystyle x}$ по модулю ${displaystyle x^{n}-1}$ .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть ${displaystyle v_{0},v_{1}}$ … могут принимать значения 0 или 1.

Порождающий полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определенному порождающему полиному ${displaystyle g(x)}$ . Порождающий полином является делителем ${displaystyle x^{n}-1}$ .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления ${displaystyle x^{n-k}u(x)}$ на ${displaystyle g(x)}$ . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома g(x) задает конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12	${displaystyle x^{12}+x^{11}+x^{3}+x^{2}+x+1}$
CRC-16	16	${displaystyle x^{16}+x^{15}+x^{2}+1}$
CRC-CCITT	16	${displaystyle x^{16}+x^{15}+x^{5}+1}$
CRC-32	32	${displaystyle x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1}$

Коды БЧХ

Коды Боуза-Чоудхури-Хоквингема (БЧХ) являются подклассом двоичных циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически построение кодов БЧХ и их декодирование используют разложение порождающего полинома ${displaystyle g(x)}$ на множители в поле Галуа.

Коды Рида-Соломона

Коды Рида-Соломона (РС-коды) фактически являются недвоичными кодами БЧХ, то есть элементы кодового вектора являются не битами, а группами битов. Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Преимущества и недостатки линейных кодов

Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.
Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.

Оценка эффективности

Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Граница Хемминга и совершенные коды

Пусть имеется двоичный блоковый ${displaystyle (n,k)}$ код с корректирующей способностью ${displaystyle t}$ . Тогда справедливо неравенство (называемое границей Хемминга):

${displaystyle sum _{i=0}^{t}{n choose i}leq 2^{n-k}}$ .

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида-Соломона) не являются совершенными.

Энергетический выигрыш

При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определенных системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.

Применение

Линейные коды применяются:

в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
в системах хранения информации, в том числе магнитных и оптических.

Линейные коды применяются в сетевых протоколах различных уровней.

См. также

Циклический код

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Линейный код. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

Источник

Линейные коды исправляющие ошибки

Обнаружение и исправление ошибок

Общие понятия

Линейные групповые коды

Definition and parameters[edit]

Generator and check matrices[edit]

Example: Hamming codes[edit]

Example: Hadamard codes[edit]

Nearest neighbor algorithm[edit]

Popular notation[edit]

Singleton bound[edit]

Bonisoli’s theorem[edit]

Examples[edit]

Generalization[edit]

See also[edit]

References[edit]

Bibliography[edit]

External links[edit]

Definition and parameters[edit]

Generator and check matrices[edit]

Example: Hamming codes[edit]

Example: Hadamard codes[edit]

Nearest neighbor algorithm[edit]

Popular notation[edit]

Singleton bound[edit]

Bonisoli’s theorem[edit]

Examples[edit]

Generalization[edit]

See also[edit]

References[edit]

Bibliography[edit]

External links[edit]

Основы

Коды обнаружения и исправления ошибок

Блоковые коды

Линейные пространства

Порождающая матрица

Проверочная матрица

Формальное определение

Свойства и важные теоремы

Минимальное расстояние и корректирующая способность

Коды Хемминга

Код Рида-Малера

Общий метод кодирования линейных кодов

Общий метод обнаружения ошибок в линейном коде

Линейные циклические коды

Порождающий полином

Коды CRC

Коды БЧХ

Коды Рида-Соломона

Преимущества и недостатки линейных кодов

Оценка эффективности

Граница Хемминга и совершенные коды

Энергетический выигрыш

Применение

См. также

А вот еще интересные материалы: