Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).

Введение

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

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем .

Алгебраическое описание

Если  — кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова , то соответствующий ему полином получается из предыдущего умножением на x:

, пользуясь тем, что

Сдвиг вправо и влево соответственно на разрядов:

Если  — произвольный полином над полем , и  — кодовое слово циклического кода, то  — тоже кодовое слово этого кода.

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

Определение

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

Теорема 1

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

где степень меньше или равна .

Теорема 2

 — порождающий полином циклического кода — является делителем двучлена .

Следствия

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

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

Полиномы линейно независимы, иначе при ненулевом , что невозможно.

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

где является порождающей матрицей,  — информационным полиномом.

Матрицу можно записать в символьной форме:

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

Для каждого кодового слова циклического кода справедливо . Поэтому проверочную матрицу можно записать как

Тогда

Кодирование

Несистематическое

При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:

Оно может быть реализовано при помощи перемножения полиномов.

Систематическое

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:

Пусть информационное слово образует старшие степени кодового слова, тогда

Тогда из условия следует

Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).

Примеры

Двоичный (7,4,3) код

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

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

где первая строка представляет собой запись полинома коэффициентами по возрастанию степени.

Остальные строки — циклические сдвиги первой строки.

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

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

Так, например, 4-й столбец получается , или в векторной записи .

Легко убедиться, что .

Двоичный (15,7,5) БЧХ код

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

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

Например, информационному слову соответствует полином , тогда кодовое слово , или в векторном виде .

См. также

Ссылки

Эта страница в последний раз была отредактирована 13 июля 2021 в 16:49.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).