Алгебраические способы и алгоритмы кодирования и декодирования (де/кодирования) кодов реализуются на основе использования элементов (принципов, правил) теории Высшей алгебры (групп, колец, матриц, суммирование по модулю два и т.д.), комбинаторики и теории вероятностей.
Достоинства способов: простота способов, алгоритмов и устройств их реализующих, большое число кодов и т.д. Недостаток - сравнительно низкая корректирующая способность многих кодов.
Арифметические способы и алгоритмы де/кодирования реализуются на основе использования теории чисел и множеств, полученных путем суммирования их по модулю некоторого "выбранного" числа. Наибольшее применение данные коды получили в ЭВМ.
Геометрические способы и алгоритмы де/кодирования реализуются на основе использования теории n-мерного пространства и проективной геометрии (коды Элайса, коды Мешковского и др.). Отличительная черта этих кодов -высокая сложность их реализации, малое число помехоустойчивых кодов; имеют ограниченное применение на практике.
Эвристические способы и алгоритмы де/кодирования базируются на основе использования определенных умозрительных логических рассуждений (коды с постоянным весом и др.). Ввиду невысокой корректирующей способности данные коды находят ограниченное применение.
Неалгебраические алгоритмы декодирования используют в основном вероятностные алгоритмы декодирования, т.е. когда при декодировании используется информация как о его полярности, так и надежности его принятия.
Данные алгоритмы обеспечивают более высокие корректирующие способности, но и имеют более высокую сложность реализации кодов.
Виды помехоустойчивых кодов.
К настоящему времени разработано достаточно большое число различных помехоустойчивых кодов, отличающихся функциональным назначением, возможностями по обнаружению и исправлению ошибок, используемыми алгоритмами кодирования и декодирования, структурой кодовых слов, избыточностью и рядом других классификационных признаков.
Прежде всего, все помехоустойчивые коды разделяются на две группы – коды, обнаруживающие ошибки и коды, исправляющие ошибки (корректирующие коды).
Коды, обнаруживающие ошибки позволяют только установить ошибочность полученной из канала кодовой комбинации.
Корректирующие коды – это коды, которые не только обнаруживают, но и исправляют в искаженных кодовых комбинациях ошибки определенной кратности.
Помехоустойчивые коды делятся на блочные и непрерывные.
Блочными называются коды, в которых последовательность информационных символов разбивается на группы и каждая из них преобразуется в определённую последовательность (блок) кодовых символов. В блочных кодах кодирование (формирование проверочных символов) и декодирование (обнаружение и исправление ошибок) выполняются в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам.
Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью символов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными или цепными.
В простейшем цепном коде каждый проверочный символ формируется путём сложения по модулю 2 двух соседних или отстоящих друг от друга на определённое число позиций информационных символов. В канал поступает последовательность символов, в которой за каждым информационным следует проверочный.
Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число символов (разрядов) – n. Равномерные коды в основном и применяются для передачи и хранения данных в АСОИиУ.
Почти все блочные коды принадлежат к разделимым кодам, в которых n – разрядные кодовые комбинации состоят из двух частей: информационной и проверочной. Их символы всегда занимают одни и те же позиции, т.е. располагаются в определённых (фиксированных) разрядах. Разновидностью разделимых кодов являются систематические коды, в которых первые m символов кодовых комбинаций являются информационными, а за ними располагаются k=(n–m) проверочных символов. Разделимые коды получили условное обозначение – (n, m) – коды.
В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким кодам относятся, в частности, равновесные коды, например, код «2 из 5».
Линейные коды образуют наиболее обширную группу (n, m)– разделимых кодов. Особенностью этих кодов является то, что проверочные (контрольные) символы образуются с помощью определенных линейных операций над информационными. Кроме того, любая разрешённая кодовая комбинация может быть получена в результате линейной операции над набором q линейно независимых кодовых комбинаций. В частности, суммирование по модулю 2 двух и более разрешённых комбинаций также дает разрешённую кодовую комбинацию. Поскольку теоретической основой получения таких комбинаций является математический аппарат линейной алгебры, то коды и называют линейными. Использование для формирования и анализа кодов аппарата линейной алгебры, в которой важное значение имеет понятие "группа", породило и другое название для этих кодов – групповые.
Линейные (групповые) получили наибольшее применение в системах передачи и хранения дискретной информации.
Нелинейные коды указанными выше свойствами не обладают и применяются значительно реже в специальных случаях. Нелинейными, в частности, являются уже упоминавшиеся неразделимые равновесные коды (Пример 2.3). Эти коды обычно используются в несимметричных каналах, в которых вероятность ошибки типа переход (конверсия) 1 → 0 значительно больше вероятности перехода 0 → 1 или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке символов были переходы обоих типов и поэтому почти все ошибки приводят к изменению числа единичных символов в блоке, и, следовательно, обнаруживаются.