Участник:Terraqottik — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Изменены разделы, добавлены ссылки)
м (Источники информации)
Строка 56: Строка 56:
 
* [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 wikipedia.org {{---}} Линейный код]
 
* [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 wikipedia.org {{---}} Линейный код]
 
* [https://en.wikipedia.org/wiki/Linear_code wikipedia.org {{---}} Linear code]
 
* [https://en.wikipedia.org/wiki/Linear_code wikipedia.org {{---}} Linear code]
* [https://scask.ru/h_book_tcod.php?id=9 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. {{---}} М: Связь, 1979. {{---}} 744 с., стр. 12-33]
+
* [https://scask.ru/h_book_tcod.php?id=3 Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. {{---}} М: Связь, 1979. {{---}} 744 с., стр. 12-33]
 
* [http://cyber.sibsutis.ru:82/monarev/docs/nauka/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%9A%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/metodichka%201.pdf Ф.И. Соловьева {{---}} Введение в теорию кодирования]
 
* [http://cyber.sibsutis.ru:82/monarev/docs/nauka/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%9A%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F/metodichka%201.pdf Ф.И. Соловьева {{---}} Введение в теорию кодирования]
 
* [https://mmf.bsu.by/wp-content/uploads/2016/10/Line_code_code_seq.pdf  В. А. Липницкий, Н. В. Чесалин {{---}} Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.]
 
* [https://mmf.bsu.by/wp-content/uploads/2016/10/Line_code_code_seq.pdf  В. А. Липницкий, Н. В. Чесалин {{---}} Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.]

Версия 09:32, 18 февраля 2021

Определение:
Линейный код (англ. Linear code) — код фиксированной длины, исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.


Линейные коды обычно делят на блочные коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.[1]

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

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

Определение:
Линейный код длины [math]n[/math] и ранга [math]k[/math] является линейным подпространством [math]C[/math] размерности [math]k[/math] векторного пространства [math]\mathbb{F}_q^n[/math], где [math]\mathbb{F}_q[/math] — конечное поле (поле Галуа) из [math]q[/math] элементов. Такой код с параметром [math]q[/math] называется [math]q[/math]-арным кодом (напр. если [math]q = 5[/math] — то это 5-арный код). Если [math]q = 2[/math] или [math]q = 3[/math], то код представляет собой двоичный код, или тернарный соответственно.


Векторы в [math]C[/math] называют кодовыми словами. Размер кода — это количество кодовых слов, т.е. [math]\mathbb{q}^k[/math].

Весом кодового слова называют число его ненулевых элементов. Расстояние между двумя кодовыми словами — это расстояние Хэмминга. Расстояние [math]d[/math] линейного кода — это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов. Линейный код длины [math]n[/math], ранга [math]k[/math] и с расстоянием [math]d[/math] называют [math][n,k,d]_q[/math]-кодом (англ. [n,k,d] code).

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

Так как линейный код является линейным подпространством [math]\mathbb{F}_q^n[/math], целиком код [math]C[/math] (может быть очень большим) может быть представлен как линейная оболочка набора из [math]k[/math] кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы [math]G[/math] и называют такую матрицу порождающей матрицей кода [math]C[/math].

В случае, если [math]\boldsymbol{G} = [I_k | P][/math], где [math]I_k[/math] — это единичная матрица размера [math]k[/math], а [math]P[/math] — это матрица размера [math]k \times (n - k)[/math] говорят, что матрица [math]G[/math] находится в каноническом виде.

Имея матрицу [math]G[/math] можно получить из некоторого входного вектора [math]s[/math] кодовое слово [math]w[/math] линейного кода [math]C[/math]

[math]w=sG[/math],

где [math]w[/math] и [math]s[/math] — векторы-строки. Порождающая матрица линейного [math][n, k, d]_q[/math]-кода имеет вид [math]k \times n[/math]. Число избыточных бит тогда определяется как [math]r = n - k[/math].

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

Линейность гарантирует, что расстояние Хэмминга [math]d[/math] между кодовым словом [math]c_0[/math] и любым другим кодовым словом [math]c \neq c_0[/math] не зависит от [math]c_0[/math]. Так как [math]c - c_0[/math] — тоже кодовое слово, а [math]d(c, c_0) = d(c - c_0, 0)[/math], то

[math]\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C,\ c \neq c_0}d(c-c_0, 0)=\min_{c \in C,\ c \neq 0}d(c, 0)=d.[/math]

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

Минимальное расстояние кода [math]d[/math] однозначно определяет количество ошибок, которое способен обнаружить ([math][{{d-1}\over{2}}][/math]) и исправить ([math]d - 1[/math]) данный код.

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

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

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

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

Примечания

Источники информации