Линейный код: различия между версиями

Перейти к навигации Перейти к поиску
Нет изменений в размере ,  6 лет назад
Нет описания правки
Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора <math>\overrightarrow{r_i}</math> вычисляется ''синдром'' <math>\overrightarrow{s_i}=\overrightarrow{r_i} H^T</math>. Поскольку <math>\overrightarrow{r_i} = \overrightarrow{v_i} + \overrightarrow{e_i}</math>, где <math>\overrightarrow{v_i}</math> — кодовое слово, а <math>\overrightarrow{e_i}</math> — вектор ошибки, то <math>\overrightarrow{s_i}=\overrightarrow{e_i} H^T</math>. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.
 
== Линейные циклические кодыкоты ==
Несмотря на то, что исправление ошибок в линейных кодах уже значительно проще исправления в большинстве нелинейных, для большинства кодов этот процесс все ещё достаточно сложен. [[Циклический код|Циклические коды]], кроме более простого декодирования, обладают и другими важными свойствами.
 
* ''систематическое кодирование'' осуществляется путём «дописывания» к кодируемому слову остатка от деления <math>x^{n-k} u(x)</math> на <math>g(x)</math>, то есть <math>v(x) = x^{n-k} u(x) + [x^{n-k} u(x) \mod g(x)]</math>.
 
=== КодыКоты CRC ===
Коды [[CRC]] (cyclic redundancy check — циклическая избыточная проверка) являются ''систематическими'' кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путём деления <math>x^{n-k} u(x)</math> на <math>g(x)</math>. Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.
 
|}
 
=== КодыКоты БЧХ ===
[[Код Боуза-Чоудхури-Хоквингема|Коды Боуза-Чоудхури-Хоквингема]] (БЧХ) являются подклассом двоичных циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.
 
Математически построение кодов БЧХ и их декодирование используют разложение порождающего полинома <math>g(x)</math> на множители в [[конечное поле|поле Галуа]].
 
=== КодыКоты Рида-Соломона ===
[[Код Рида-Соломона|Коды Рида-Соломона]] (РС-коды) фактически являются ''недвоичными'' кодами БЧХ, то есть элементы кодового вектора являются не битами, а группами битов. Очень распространены коды Рида-Соломона, работающие с [[байт]]ами ([[октет (информатика)|октетами]]).
 
== Преимущества и недостатки линейных кодовкотов ==
+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
 
Эффективность кодов определяется количеством ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для [[ЭВМ]]).
 
=== Граница Хемминга и совершенные кодыкоты ===
{{main|Граница Хэмминга}}
Пусть имеется двоичный блоковый <math>(n,k)</math> код с корректирующей способностью <math>t</math>. Тогда справедливо неравенство (называемое ''границей Хемминга''):
Анонимный участник

Навигация