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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Расстояние кода)
(Изменены разделы, добавлены ссылки)
Строка 5: Строка 5:
 
Линейные коды обычно делят на блочные коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.<ref>[https://archive.org/details/channelcodesclas00ryan/page/n21 William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.]</ref>
 
Линейные коды обычно делят на блочные коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.<ref>[https://archive.org/details/channelcodesclas00ryan/page/n21 William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.]</ref>
  
По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. синдромы ошибок).
+
По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. [[Участник:Terraqottik#Синдромы и метод обнаружения ошибок в линейном коде | синдромы ошибок]]).
  
 
== Формальное определение ==
 
== Формальное определение ==
Строка 37: Строка 37:
 
Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.
 
Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.
  
== Количество ошибок ==
+
Минимальное расстояние кода <tex>d</tex> [[Избыточное кодирование, код Хэмминга#Определение и устранение ошибок в общем случае | однозначно определяет]] количество ошибок, которое способен обнаружить (<tex>[{{d-1}\over{2}}]</tex>) и исправить (<tex>d - 1</tex>) данный код.
  
== Прочее ==
+
== Синдромы и метод обнаружения ошибок в линейном коде ==
 +
 
 +
 
 +
 
 +
== Преимущества и недостатки линейных кодов ==
 +
 
 +
+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
 +
 
 +
- Хотя линейные коды, как правило, хорошо справляются с редкими, но большими ''пачками ошибок'', их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.
  
 
== Примечания ==
 
== Примечания ==

Версия 09:29, 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]) данный код.

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

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

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

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

Примечания

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