Документация

Функции CRC-кода

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

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

Откройте Выявление ошибок и Коррекцию библиотеку, дважды щелкнув ее значок в основной библиотеке блоков Communications Toolbox™. Откройте сублибрарий CRC, дважды щелкнув по его значку в библиотеке Выявления ошибок и Коррекции.

Communications Toolbox поддерживает CRC-кодирование с использованием Simulink^® блоки, системные объекты или MATLAB^® объекты. Эти функции CRC-кодирования перечислены в Выявление ошибок и Коррекцию.

Алгоритм CRC Non-Direct

CRC непрямой алгоритм принимает двоичный вектор данных, соответствующий полиному M, и добавляет контрольную сумму r бит, соответствующую полиному C. Конкатенация вектора входа и контрольной суммы затем соответствует полиному T = M *x^r + C, с момента умножения на x^r соответствует тому, перемена вектор входа r битами налево. Алгоритм выбирает контрольную сумму C так что T делится на предопределенную полиномиальную P степени r, называемую полиномом генератора.

Алгоритм делит T на P и устанавливает контрольную сумму, равную двоичному вектору, соответствующему остатку. То есть, если T = Q *P + R, где R является полиномом степени меньше r, контрольная сумма является двоичным вектором, соответствующим R. При необходимости алгоритм подготавливает нули к контрольной сумме так, чтобы она имела длину r.

Функция генерации CRC, которая реализует фазу передачи алгоритма CRC, делает следующее:

Функция обнаружения CRC вычисляет контрольную сумму для всего своего входного вектора, как описано выше.

Алгоритм CRC использует двоичные векторы, чтобы представлять двоичные полиномы в порядке убывания степеней. Для примера, вектор [1 1 0 1] представляет полином x³ + x² + 1.

Биты поступают в регистр сдвига линейной обратной связи (LFSR) с самого нижнего бита индекса на самый высокий бит индекса. Последовательность входа бит сообщения представляет коэффициенты полинома сообщения в порядке уменьшения степеней. Вектор сообщения дополнен нулями r чтобы смыть LFSR, где r - степень полинома генератора. Если выход от крайнего левого каскада регистра d (1) равен 1, то биты в регистре сдвига имеют значение XOR с коэффициентами полинома генератора. Когда дополненная последовательность сообщений полностью отправляется через LFSR, регистр содержит контрольную сумму [d (1) d (2). d (r)]. Это реализация двоичного длинного деления, в котором последовательность сообщений является делителем (числителем), а полином является дивидендом (знаменателем). Контрольная сумма CRC является оставшейся частью операции деления.

Пример использования алгоритма CRC Non-Direct

Предположим, что входной кадр [1 1 0 0 1 1 0]', соответствующий полиному M = x⁶ + x⁵ + x² + x, и полином генератора является P = x³ + x² + 1, степени r = 3. Путем полиномиального деления M *x³ = (x⁶ + x³ + x) *P + x. Остаток R = x, так что контрольная сумма затем [0 1 0]'. Слева добавляется дополнительный 0, чтобы контрольная сумма имела длину 3.

Прямой алгоритм CRC

где

Вход блока сообщения: $$m_0,m_1,\mathrm{...},m_{k-1}$$

Выход кодового слова: $$c_0,c_1,\mathrm{...}\text{}\text{},\text{}{c}_{n-1}=\underset{X}{\underbrace{m_0,m_1,\mathrm{...}\text{}\text{},m_{k-1},}}\underset{Y}{\underbrace{d_0,d_1,\mathrm{...},d_{n-k-1}}}$$

Начальный шаг прямого кодирования CRC происходит с тремя переключателями в положении X. Алгоритм k биты сообщений в энкодер. Эти биты являются первыми k битами кода слова выхода. Одновременно алгоритм отправляет k бит в линейный регистр сдвига с обратной связью (LFSR). Когда система полностью подает k бит сообщения в LFSR, переключатели перемещаются в положение Y. Здесь LFSR содержит математический остаток от полиномиального деления. Эти биты смещены из LFSR, и они являются оставшимися битами (контрольной суммой) выходного кодового слова.

Выбранная библиография для CRC-кодирования

Функции блочного кодирования

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

Блочное кодирование является частным случаем кодирования с управлением ошибками. Методы блочного кодирования сопоставляют фиксированное количество символов сообщения с фиксированным количеством кодовых символов. Блочный кодер обрабатывает каждый блок данных независимо и является незапамятным устройством. Communications Toolbox содержит возможности блочного кодирования путем предоставления блоков Simulink, системных объектов и функций MATLAB.

Класс методов блочного кодирования включает категории, показанные на схеме ниже.

Communications Toolbox поддерживает общие линейные блочные коды. Он также обрабатывает циклические, BCH, Hamming и Рид-Соломоновы коды (которые являются всеми специальными видами линейных блочных кодов). Блоки в продукте могут кодировать или декодировать сообщение с помощью одного из вышеупомянутых методов. Декодеры Рида-Соломона и BCH указывают, сколько ошибок они обнаружили во время декодирования. Блоки кодирования Рида-Соломона также позволяют вам решить, использовать ли символы или биты в качестве ваших данных.

Функции поддержки Communications Toolbox.  Функции в Communications Toolbox могут поддерживать блоки симуляции

Для получения дополнительной информации о возможностях кодирования с управлением ошибками смотрите Блочные коды.

Терминология

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

Каждый блок K символов сообщения кодируется в кодовое слово, которое состоит из N символов сообщения. K называется длиной сообщения, N называется длиной кодового слова, а код называется кодом [N, K].

Форматы данных для блочного кодирования

Каждое сообщение или кодовое слово является упорядоченной группировкой символов. Каждый блок в подлибрарии блочного кодирования обрабатывает по одному слову на каждом временном шаге, как описано в следующем разделе «Двоичный формат (все методы кодирования)». Блоки кодирования Рида-Соломона также позволяют вам выбирать между двоичными и целыми данными, как описано в Целочисленном Формате (только для Рида-Соломона).

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

Этот пример иллюстрирует энкодер, принимающий четырехбитовое сообщение и выдающий пятибитовое кодовое слово во время 0. Он повторяет этот процесс с новым сообщением в момент 1.

Для всех методов кодирования, кроме Рида-Соломона, использующих двоичный вход, вектор сообщения должен иметь длину K, и соответствующий вектор кода имеет длину N. Для кодов Рида-Соломона с двоичным входом символы для кода являются двоичными последовательностями длины M, соответствующими элементам поля Галуа GF (2^M). В этом случае вектор сообщения должен иметь длину M * K, и соответствующий вектор кода имеет длину M * N. Блок Binary-Input RS Encoder и блок Binary-Output RS Decoder используют этот формат для сообщений и кодовых слов.

Если вход в блок блочного кодирования является вектором на основе фрейма, это должен быть вектор-столбец вместо вектора-строки.

Чтобы создать сообщения на основе выборок в двоичном формате, можно сконфигурировать блок Bernoulli Binary Generator так, чтобы его параметр Probability of a zero был вектором, длина которого является длиной сигнала, который вы хотите создать. Чтобы создать сообщения на основе фрейма в двоичном формате, можно сконфигурировать тот же блок так, чтобы его параметр Probability of a zero был скаляром, а его параметр Samples per frame был длиной сигнала, который вы хотите создать.

Использование последовательных сигналов

Если вы предпочитаете структурировать сообщения и кодовые слова как скалярные сигналы, где несколько выборок совместно образуют слово сообщения или кодовое слово, можно использовать блоки Buffer и Unbuffer. Буферизация включает задержку и многократную обработку. Если ваша модель вычисляет частоты ошибок, начальная задержка в комбинации кодирования и буферизации влияет на параметр Receive delay в блоке Error Rate Calculation.

Вы можете отобразить шаги расчета сигналов в вашей модели. На вкладке Debug разверните Information Overlays. В Sample Time разделе выберите Colors. Кроме того, можно присоединить блоки Probe (Simulink) к линиям соединителя, чтобы помочь оценить время расчета выборки, буферизацию и задержки.

Целочисленный формат (только для Рида-Соломона).  Сообщение для кода [N, K] Рида-Соломона состоит из M * K биты, которые можно интерпретировать как K символов от 0 до 2^M. Символы являются двоичными последовательностями длины M, соответствующими элементам поля Галуа GF (2^M), в порядке убывания степеней. Целочисленный формат для кодов Рида-Соломона позволяет структурировать сообщения и кодовые слова как целочисленные сигналы вместо двоичных сигналов. (Входной вход должен быть вектором-столбцом на основе фрейма.)

Следующий рисунок иллюстрирует эквивалентность между двоичными и целое число сигналами для энкодера Рида-Соломона. Случай для декодера аналогичен.

Чтобы создать сообщения на основе выборок в целочисленном формате, можно сконфигурировать блок Random Integer Generator так, чтобы M-ary number и Initial seed параметры были векторами желаемой длины, и все значения вектора M-ary number были 2^M. Чтобы создать сообщения на основе фрейма в целочисленном формате, можно сконфигурировать один и тот же блок так, чтобы его M-ary number и параметры Initial seed были скалярами, а его параметр Samples per frame был длиной сигнала, который вы хотите создать.

Использование блочных энкодеров и декодеров в модели

После того, как вы сконфигурировали блоки кодирования, несколько советов могут помочь вам правильно поместить их в свою модель:

Примеры Блока кодирования

Пример: Код Рида-Соломона в целочисленном формате.  Этот пример использует код Рида-Соломона в целочисленном формате. Он иллюстрирует соответствующие длины вектора кода и сигналов сообщения для блоков кодирования. Это также показывает коррекцию ошибок, используя простой способ введения ошибок в каждое кодовое слово.

Откройте модель путем набора doc_rscoding в командной строке MATLAB. Чтобы создать модель, соберите и сконфигурируйте эти блоки:

Соедините блоки как показано на предыдущем рисунке. На вкладке Simulation, в разделе Simulate, установите Stop time равным 500. Раздел Simulate появляется на нескольких вкладках.

Вы можете отобразить длину вектора сигналов в своей модели. На вкладке Debug разверните Information Overlays. В Signals разделе выберите Signal Dimensions.

Энкодер принимает вектор длины 5 (в этом случае это K) и производит вектор длины 15 (в этом случае это N). Декодер делает обратное.

Выполнение модели создает следующие изображения возможностей. Количество нанесенных на график ошибок будет варьироваться в зависимости от Initial Seed значения, используемого в блоке Random Integer Generator. Диапазон осей можно настроить, точно совпадая с областью значений первых возможностей. Щелкните правой кнопкой мыши область графика во вторых возможностях и выберите Configuration Properties. На вкладке Display измените пределы осей.

Второй график - это количество ошибок, обнаруженных декодером при попытке восстановить сообщение. Часто число составляет пять, потому что блок Gain заменяет первые пять символов в каждом кодовом слове нулями. Однако количество ошибок меньше пяти, когда правильное кодовое слово содержит одно или несколько нулей в первых пяти местах.

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

Заметки о конкретных методах блочного кодирования

Несмотря на то, что подлибрарий блочного кодирования является несколько равномерным по своему внешнему виду и чувству, различные методы кодирования не идентичны. В этом разделе описываются специальные опции и ограничения, которые применяются к параметрам и сигналам для категорий метода кодирования в этом сублибрарии. Методы кодирования, обсуждаемые ниже, включают - типовой линейный блочный код, циклический код, хемминговый код, код BCH и код Рида-Соломона.

Типовые линейные коды Блока

Для кодирования сообщения с помощью типового линейного блочного кода требуется матрица генератора. Для декодирования кода требуется матрица генератора и, возможно, таблица истинности. Чтобы использовать блоки Binary Linear Encoder и Binary Linear Decoder, вы должны понять параметры Generator matrix и Error-correction truth table.

Матрица Генератора - Процесс кодирования сообщения в линейный блочный код [N, K] определяется матрицей G. В частности, вектор v 1-by-K сообщения кодируется в вектор vG 1-by-N кодового слова. Если G имеет вид [_Ik, P] или [P, _Ik], где P является некоторой K-by- (N-K) матрицей, а Ik является K-by-K тождеств матрицей, G называется в стандартной форме. (Некоторые авторы, такие как Clark и Cain [2], используют первую стандартную форму, другие же, такие как Lin и Costello [3], используют вторую.) Блоки линейного блочного кодирования в этом продукте требуют, чтобы параметр Generator matrix mask был в стандартной форме.

Таблица декодирования - таблица декодирования сообщает декодеру, как исправить ошибки, которые могли испортить код во время передачи. Хемминговые коды могут исправить любую односимвольную ошибку в любом кодовом слове. Другие коды могут исправлять или частично исправлять ошибки, которые повреждают более одного символа в заданном кодовом слове.

Блок Binary Linear Decoder позволяет вам задать таблицу декодирования в параметре Error-correction truth table. Представьте таблицу декодирования как матрицу с N столбцами и 2^N-K строки. Каждая строка задает вектор коррекции для одного полученного вектора кодового слова.

Можно избежать явного задания таблицы декодирования, задав значение параметра Error-correction truth table 0. Когда Error-correction truth table 0, блок вычисляет таблицу декодирования, используя syndtable функция.

Циклические коды

Для циклических кодов длина кодового слова N должна иметь вид 2^M-1, где M является целым числом, большим или равным 3.

Полиномы Генератора - Циклические коды имеют специальные алгебраические свойства, которые позволяют полиному полностью определить процесс кодирования. Этот так называемый полином генератора является степени- (N-K) делителем многочлена x^N-1. Ван Линт [5] объясняет, как полином генератора определяет циклический код.

Блоки Binary Cyclic Encoder и Binary Cyclic Decoder позволяют вам задать полином генератора в качестве параметра второй маски, вместо того, чтобы задавать там K. Блоки представляют полином генератора, используя вектор, который перечисляет коэффициенты многочлена в порядке возрастания степеней переменной. Полиномы генератора для циклических кодов можно найти, используя cyclpoly функция.

Если вы не хотите задавать полином генератора, задайте значение параметра второй маски K.

Коды Хемминга

Для кодов Hamming длина кодового слова N должна иметь вид 2^M-1, где M является целым числом, большим или равным 3. Длина сообщения K должна равняться N-M.

Примитивные полиномы - Коды Хемминга полагаются на алгебраические поля, которые имеют 2^M элементы (или, в более общем виде, p^M элементы для простого числа p). Элементы таких полей названы относительно различимого элемента поля, который называется примитивным элементом. Минимальный полином примитивного элемента называется примитивным полиномом. Блоки Hamming Encoder и Hamming Decoder позволяют вам задать примитивный полином для конечного поля, которое они используют для расчетов. Если вы хотите задать этот полином, сделайте это в поле второго параметра маски. Блоки представляют примитивный полином, используя вектор, который перечисляет коэффициенты многочлена в порядке возрастания степеней переменной. Вы можете найти полиномы генератора для полей Галуа, используя gfprimfd функция.

Если вы не хотите задавать примитивный полином, задайте значение параметра второй маски K.

Коды BCH

Коды BCH являются циклическими кодами с исправлением ошибок, которые строятся с использованием конечных полей. Для этих кодов длина кодового слова N должна иметь вид 2^M-1, где M является целым числом от 3 до 9. Длина сообщения K ограничена конкретными значениями, которые зависят от N. Чтобы увидеть, какие значения K действительны для заданного N, смотрите comm.BCHEncoder Система object™ страницы с описанием. Неизвестная аналитическая формула не описывает отношение между длиной кодового слова, длиной сообщения и возможностью исправления ошибок для кодов BCH.

Узкополосные коды BCH

Полином генератора с узким смыслом является LCM [m _ 1 (x), m_2 (x),..., m_2t (x)], где:

Коды Рида-Соломона

Коды Рида-Соломона полезны для исправления ошибок, происходящих в пакетах. В самом простом случае длина кодовых слов в коде Рида-Соломона имеет вид N = 2^M-1, где 2^M - количество символов для кода. Возможность исправления ошибок кода Рида-Соломона floor((N-K)/2), где K - длина слов сообщения. Значение различия N-K должно быть четным.

Иногда удобно использовать укороченный код Рида-Соломона, в котором N меньше 2^M-1. В этом случае энкодер добавляет 2^M-1-N нулевые символы к каждому сообщению и кодовому слову. Возможность исправления ошибок укороченного кода Рида-Соломона также floor((N-K)/2). Блоки Communications Toolbox Рида-Соломона могут реализовать укороченные коды Рида-Соломона.

Эффект небинарных символов - Одно различие между кодами Рида-Соломона и другими кодами, поддерживаемыми в этом продукте, заключается в том, что коды Рида-Соломона обрабатывают символы в GF (2^M) вместо GF (2). M бит задают каждый символ. Небинарная природа символов Рида-Соломона кода заставляет блоки Рида-Соломона отличаться от других блоков кодирования следующими способами:

Информация об ошибке - Блоки декодирования Рида-Соломона (Binary-Output RS Decoder и Integer-Output RS Decoder) возвращают информацию, связанную с ошибкой, во время симуляции. Второй выход сигнал указывает количество ошибок, которые блок обнаружил в вход кодовом слове. A-1 во втором выходе указывает, что блок обнаружил больше ошибок, чем мог исправить, используя схему кодирования.

Укорочение, прокалывание и стирание

Многие стандарты используют проколотые коды, и цифровые приемники могут легко выводить стирания. BCH и RS эффективности значительно улучшаются в каналах с замираниями, где приемник генерирует стирания.

Проколотое кодовое слово имеет удаленные только символы четности, а укороченное кодовое слово имеет удаленные только информационные символы. Кодовое слово с стираниями может иметь эти стирания как в информационных символах, так и в символах четности.

Примеры Рида Соломона с укорочением, проколом и стиранием

В этом разделе демонстрационный пример кодирования Рида Соломона с укорочением, проколом и стираниями построен с увеличением сложности коррекции ошибок.

Пример энкодера с укорочением и проколом

Следующие рисунки показывают демонстрационный пример (7,3) Рида Соломона с энкодером укорочения и прокола.

На этом рисунке источник сообщения выводит два информационных символа, обозначенных _I1I2. (Для примера BCH символы являются двоичными битами.) Поскольку код является укороченным (7,3) кодом, нуль должен быть добавлен перед информационными символами, получая трехсимвольное сообщение _0I1I2. Измененная последовательность сообщений кодируется RS, и затем добавляемая информация нули удаляется, что приводит к результату _I1I2P1P2P3P4. (В этом примере биты четности находятся в конце кодового слова.)

Операция прокола управляется вектором прокола, который в этом случае равен 1011. В векторе пункции a 1 означает, что символ сохранен, и 0 означает, что символ выбрасывается. В этом примере операция прокалывания удаляет второй символ четности, получая конечный вектор _I1I2P1P3P4.

Пример декодера с укорочением и проколом

Следующий рисунок показывает, как RS-декодер работает с укороченным и проколотым кодовым словом.

Этот случай соответствует операциям энкодера, показанным на рисунке RS-энкодера с укорочением и проколом. Как показано на предыдущем рисунке, энкодер принимает (5,2) кодовое слово, поскольку оно было укорочено от (7,3) кодового слова одним символом, и один символ также был проколот.

В качестве первого шага декодер добавляет стирание, обозначенное E, во второе положение четности кодового слова. Это соответствует вектору 1011 прокола. Добавление нуля учитывает сокращение, таким же образом как показано на предыдущем рисунке. Одно стирание не превышает возможности исправления стирания кода, что может исправить четыре стирания. Операция декодирования результатов в трехсимвольном сообщении _DI1I2. Первый символ усечен, как и на предыдущем рисунке, получая конечный выход _I1I2.

Пример декодера с укорочением, прокалыванием и стиранием

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

На этом рисунке демодулятор получает вектор _I1I2P1P3P4, который подает энкодер Демодулятор заявляет, что два из пяти принятых символов являются достаточно ненадежными, чтобы быть стерты, так что символы 2 и 5 считаются стираниями. Вектор 01001, обеспечиваемый внешним источником, указывает на эти стирания. В векторе стирания значение 1 означает, что символ должен быть заменен символом стирания, а значение 0 означает, что символ передается без изменений.

Декодер блокирует прием кодового слова и вектора стирания и выполняет стирание, обозначенное вектором 01001. В векторе стирания значение 1 означает, что символ должен быть заменен символом стирания, а значение 0 означает, что символ передается без изменений. Получившийся вектор кодового слова _I1EP1P3E, где E является символом стирания.

Кодовое слово затем деформируется в соответствии с вектором прокола, используемым в операции кодирования (т.е. 1011). Таким образом, символ стирания вставляется между _P1 и _P3, получая вектор _I1EP1EP3E кодового слова.

Непосредственно перед декодированием сложение нулей в начале информационного вектора учитывает сокращение. Получившийся вектор _0I1EP1EP3E, так что (7,3) кодовое слово посылается в алгоритм Берлекампа.

Это кодовое слово декодируется, получая трехсимвольное сообщение _DI1I2 (где D относится к фиктивному символу). Наконец, удаление символа D из вектора сообщения учитывает сокращение и приводит к выражениям исходного вектора _I1I2.

Для получения дополнительной информации смотрите пример Reed-Solomon Coding with Erasures, Portures и Shortening MATLAB или пример Reed-Solomon Coding with Erasures, Portures и Shortening in Simulink.

Код Рида-Соломона в целом формате

Чтобы открыть пример модели, которая использует код Рида-Соломона в целочисленном формате, введите doc_rscoding в командной строке MATLAB. Для получения дополнительной информации о модели смотрите Пример: Код Рида-Соломона в целочисленном формате

Найдите полином генератора

Чтобы найти полином генератора для циклического, BCH или кода Рида-Соломона, используйте cyclpoly, bchgenpoly, или rsgenpoly функция, соответственно. Команды

genpolyCyclic = cyclpoly(15,5) % 1+X^5+X^10
genpolyBCH = bchgenpoly(15,5)  % x^10+x^8+x^5+x^4+x^2+x+1
genpolyRS = rsgenpoly(15,5)

найти полиномы генератора для блочных кодов разных типов. Ниже приведен выход.

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1


genpolyBCH = GF(2) array.

Array elements =

     1     0     1     0     0     1     1     0     1     1     1


genpolyRS = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     1     4     8    10    12     9     4     2    12     2     7

Форматы этих выходов варьируются:

Неоднородность полиномов генератора

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

Алгебраическое выражение для полиномов генератора

Полиномы генератора, произведенные bchgenpoly и rsgenpoly иметь форму (X - A^b) ( X - A^b+1)... ( X - A^b+2t-1), где A является примитивным элементом для соответствующего поля Галуа, и b и t являются целыми числами. Для получения дополнительной информации об этом выражении см. страницы с описанием функций.

Выполнение других задач блочного кода

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

Выбранная библиография для блочного кодирования

Функции сверточного кода

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

Communications Toolbox предоставляет возможности сверточного кодирования как блоки Simulink, системные объекты и функции MATLAB. Этот продукт поддерживает сверточные коды с feedforward и обратной связью, которые могут быть описаны решетчатой структурой или набором полиномов генератора. Он использует алгоритм Viterbi, чтобы реализовать декодирование с твердым и мягким решениями.

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

Справочную информацию о сверточном кодировании см. в работах, перечисленных в Selected Bibliography for Convolutional Coding.

Параметры блоков для сверточного кодирования

Для обработки сверточных кодов используйте блоки Convolutional Encoder, Viterbi Decoder и/или APP Decoder в Подсобке сверток. Если параметр маски требуется как в энкодере, так и в декодере, используйте одно и то же значение в обоих блоках.

Блоки в Сверточной сублибрарии предполагают, что вы используете одно из двух различных представлений сверточного энкодера:

Для получения дополнительной информации об этих представлениях, смотрите Полином Описание сверточного кода и Trellis Описание сверточного кода.

Использование полиномиального описания в блоках

Чтобы использовать полиномиальное описание с Convolutional Encoder, Viterbi Decoder или APP Decoder блоками, используйте служебную функцию poly2trellis из Communications Toolbox. Эта функция принимает полиномиальное описание и преобразует его в описание шпалеры. Для примера следующая команда вычисляет описание шпалеры энкодера, длина ограничения которого равна 5, а полиномы генератора - 35 и 31:

trellis = poly2trellis(5,[35 31]);

Чтобы использовать этот энкодер с одним из блоков сверточного кодирования, просто поместите poly2trellis команду, такую как

poly2trellis(5,[35 31]);

в поле параметра Trellis structure.

Полиномиальное описание сверточного кода

Полиномиальное описание сверточного энкодера описывает связи между регистрами сдвига и сумматорами по модулю 2. Для примера рисунок ниже изображает feedforward сверточный энкодер, который имеет один вход, два выхода и два регистра сдвига.

Полиномиальное описание сверточного энкодера имеет или два, или три компонента, в зависимости от того, является ли энкодер типом с прямой или обратной связью:

Длины ограничений.  Длины ограничений энкодера образуют вектор, длина которого является количеством входов в схеме энкодера. Элементы этого вектора указывают количество битов, сохраненных в каждом регистре сдвига, включая текущие входные биты.

На рисунке выше длина ограничения равна трем. Это скаляр, потому что энкодер имеет один входной поток, и его значение составляет один плюс количество регистров сдвига для этого входа.

Генератор Полиномов.  Если схема энкодера имеет k входов и n выходов, матрица генератора кода является k-на-n матрицей. Элемент в i-й строке и j-ом столбце указывает, как i-й вход вносит вклад в j-й выход.

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

В других ситуациях можно определить (i, j) запись в матрице следующим образом:

Для примера двоичные числа, соответствующие верхнему и нижнему сумматорам на рисунке выше, составляют 110 и 111 соответственно. Эти двоичные числа эквивалентны октальным числам 6 и 7, соответственно, поэтому полиномиальная матрица генератора является [6 7].

Таблица некоторых хороших генераторов сверточного кода приведена в [2] в разделе «Выбранная библиография для блочного кодирования», особенно в приложениях к этой книге.

Полиномы связи с обратной связью.  Если вы представляете энкодер обратной связи, вам нужен вектор полиномов связи с обратной связью. Длина этого вектора является количеством входов в схеме энкодера. Элементы этого вектора указывают соединение с обратной связью для каждого входа, используя восьмиугольный формат. Сначала создайте представление двоичного числа, как на шаге 1 выше. Затем преобразуйте двоичное представление в октальное представление, как на шаге 2 выше.

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

Используйте структуру Trellis для сверточного энкодера скорости 1/2 с обратной связью

Создайте решетчатую структуру, чтобы представлять систематический сверточный энкодер скорости 1/2 с обратной связью, показанной на этой схеме.

Этот энкодер имеет 5 для своей ограничительной длины, [37 33] как его полиномиальная матрица генератора и 37 для его полинома связи с обратной связью.

Первый полином генератора является восьмиугольным 37. Второй полином генератора является восьмиугольным 33. Полином обратной связи является восьмиугольным 37. Первый полином генератора совпадает с полиномом связи с обратной связью, потому что первый выход соответствует систематическим битам.

Двоичный вектор [1 1 1 1 1] представляет восьмеричный 37 и соответствует верхней строке двоичных цифр в схеме. Двоичный вектор [1 1 0 1 1] представляет восьмеричный 33 и соответствует нижней строке двоичных цифр в схеме. Эти двоичные цифры указывают на соединения с выходами регистров к двум сумматорам в схеме. Начальный 1 соответствует вход биту.

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

trellis = poly2trellis(5,[37 33],37)

trellis = struct with fields:
     numInputSymbols: 2
    numOutputSymbols: 4
           numStates: 16
          nextStates: [16x2 double]
             outputs: [16x2 double]

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

data = randi([0 1],70,1);
codedData = convenc(data,trellis);
tbdepth = 34; % Traceback depth for Viterbi decoder
decodedData = vitdec(codedData,trellis,tbdepth,'trunc','hard');

Проверьте, что декодированные данные имеют нулевые битовые ошибки.

biterr(data,decodedData)

ans = 0

Использование полиномиального описания в MATLAB.  Чтобы использовать полиномиальное описание с функциями convenc и vitdec, сначала преобразуйте его в описание шпалеры, используя poly2trellis функция. Для примера команда ниже вычисляет описание шпалеры энкодера, изображенное в разделе Полином Описание сверточного кода.

trellis = poly2trellis(3,[6 7]);

Структура MATLAB trellis является подходящим входным параметром для convenc и vitdec.

Описание шпалеры сверточного кода

Описание решетки сверточного энкодера показывает, как каждый возможный вход в энкодер влияет как на выход, так и на состояние перехода энкодера. В этом разделе описываются шпалеры, и как представлять шпалеры в MATLAB, и приводится пример шпалеры MATLAB.

Рисунок ниже изображает решетку для сверточного энкодера из предыдущего раздела. Энкодер имеет четыре состояния (пронумерованы в двоичном формате от 00 до 11), однобитовый вход и двухбитовый выход. (Отношение входных битов к выходным битам делает этот энкодер энкодером скорости 1/2.) Каждая стрела показывает, как энкодер изменяет свое состояние, если текущий вход равен нулю, и каждая штриховая стрела показывает, как энкодер изменяет свое состояние, если текущий вход равен единице. Восьмеричные числа над каждой стрелой указывают на текущий выход энкодера.

В качестве примера интерпретации этой решетчатой схемы, если энкодер находится в состоянии 10 и получает вход нуля, он выводит кодовый символ 3 и изменяется на состояние 01. Если он находится в 10 состоянии и получает вход единицы, он выводит кодовый символ 0 и изменяется в 11 состоянии.

Обратите внимание, что любое полиномиальное описание сверточного энкодера эквивалентно некоторому описанию шпалеры, хотя некоторые шпалеры не имеют соответствующих полиномиальных описаний.

Задание триллиса в MATLAB.  Чтобы задать шпалеру в MATLAB, используйте определенную форму структуры MATLAB, называемую структурой шпалеры. Решетчатая структура должна иметь пять полей, как в таблице ниже.

В nextStates матрица, каждая запись является целым числом от 0 до numStates-1. Элемент в i-й строке и j-ом столбце обозначает следующее состояние, когда начальное состояние является i-1, и входные биты имеют десятичное представление j-1. Чтобы преобразовать входные биты в десятичное значение, используйте первый входной бит как самый значащий бит (MSB). Например, второй столбец nextStates матрица сохраняет следующие состояния, когда текущий набор значений входа {0,..., 0,1}. Чтобы узнать, как назначить номера состояниям, смотрите страницу с описанием дляistrellis.

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

Создание структуры шпалеры MATLAB.  Как только вы знаете, какую информацию хотите поместить в каждое поле, можно создать решетчатую структуру любым из следующих способов:

Чтобы проверить, является ли ваша структура допустимой решетчатой структурой, используйте istrellis функция.

Пример: Структура шпиля MATLAB.  Рассмотрим решетку, показанную ниже.

Чтобы создать структуру шпалеры, которая ее опишет, используйте команду ниже.

trellis = struct('numInputSymbols',2,'numOutputSymbols',4,...
'numStates',4,'nextStates',[0 2;0 2;1 3;1 3],...
'outputs',[0 3;1 2;3 0;2 1]);

Количество входа символов составляет 2, потому что решетчатая схема имеет два типа входа пути: твердотельная стрела и штриховой стрелы. Количество выхода символов составляет 4, потому что числа выше стрел могут быть 0, 1, 2 или 3. Количество состояний равно 4, потому что с левой стороны решетчатой схемы четыре пули (эквивалентно, четыре с правой стороны). Чтобы вычислить матрицу следующих состояний, создайте матрицу, строки которой соответствуют четырем текущим состояниям на левой стороне шпалеры, столбцы которой соответствуют входам 0 и 1, и элементы которой дают следующие состояния в конце стрел на правой стороне шпалеры. Чтобы вычислить матрицу выходов, создайте матрицу, строки и столбцы которой как в матрице следующих состояний, но элементы которой дают восьмеричные выходные параметры, показанные над стрелами в решетке.

Создайте и декодируйте сверточные коды

Функции для кодирования и декодирования сверточных кодов convenc и vitdec. В этом разделе рассматривается использование этих функций для создания и декодирования сверточных кодов.

Кодировка.  Простой способ использования convenc создание сверточного кода показано в приведенных ниже командах.

Задайте шпалеру.

t = poly2trellis([4 3],[4 5 17;7 4 2]);

Закодируйте вектор таковых.

x = ones(100,1);
code = convenc(x,t);

Первая команда преобразует полиномиальное описание сверточного энкодера с прямой связью в соответствующее описание шпалеры. Вторая команда кодирует 100 биты или 50 двухбитовых символов. Поскольку скорость кода в этом примере является 2/3, вектор выхода code содержит 150 биты (то есть 100 входных биты умножить на 3/2).

Чтобы проверить, соответствует ли ваша шпалера катастрофическому сверточному коду, используйте iscatastrophic функция.

Декодирование с жестким решением.  Чтобы декодировать, используя жесткие решения, используйте vitdec функция с флагом 'hard' и с двоичными входными данными. Потому что выход convenc является двоичным, декодирование с жестким решением может использовать выход convenc непосредственно, без дополнительной обработки. Этот пример расширяет предыдущий пример и реализует декодирование с жестким решением.

Задайте шпалеру.

t = poly2trellis([4 3],[4 5 17;7 4 2]);

Закодируйте вектор таковых.

code = convenc(ones(100,1),t);

Установите длину трассировки для декодирования и декодирования с помощью vitdec.

tb = 2;
decoded = vitdec(code,t,tb,'trunc','hard');

Проверьте, что декодированные данные являются вектором 100 таковых.

isequal(decoded,ones(100,1))

ans = logical
   1

Декодирование с мягким решением.  Чтобы декодировать с помощью мягких решений, используйте vitdec функция с флагом 'soft'. Задайте число, nsdec, биты и использование входных данных, состоящих из целых чисел от 0 до 2^nsdec-1.

Вход 0 представляет наиболее уверенное 0, в то время как вход 2^nsdec-1 представляет наиболее уверенный 1. Другие значения представляют собой менее уверенные в себе решения. Для примера в таблице ниже перечислены интерпретации значений для 3-битных мягких решений.

Реализуйте декодирование с мягким решением с использованием MATLAB

Скрипт ниже иллюстрирует декодирование с 3-битными мягкими решениями. Сначала он создает сверточный код с convenc и добавляет белый Гауссов шум в код с awgn. Затем, чтобы подготовиться к декодированию с мягким решением, пример использует quantiz сопоставить значения зашумленных данных с соответствующими целыми числами решающего значения в диапазоне от 0 до 7. Второй аргумент в quantiz вектор секционирования, который определяет, какие значения данных сопоставлены с 0, 1, 2 и т.д. Раздел выбран так, чтобы значения около 0 сопоставлялись с 0, а значения около 1 совпадали с 7. (Можно уточнить раздел, чтобы получить лучшую эффективность декодирования, если это требуется приложению.) Наконец, пример декодирует код и вычисляет вероятность битовой ошибки. При сравнении декодированных данных с исходным сообщением в примере должна учитываться задержка декодирования. Режим непрерывной операции vitdec вызывает задержку, равную длине обратного вызова, поэтому msg(1) соответствует decoded(tblen+1) вместо того, чтобы decoded(1).

s = RandStream.create('mt19937ar', 'seed',94384);
prevStream = RandStream.setGlobalStream(s);
msg = randi([0 1],4000,1); % Random data
t = poly2trellis(7,[171 133]); % Define trellis.
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(t);
% Create an AWGNChannel System object.
hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',...
  'SNR', 6);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Soft', ...
    'SoftInputWordLength', 3, 'TracebackDepth', 48, ...
    'TerminationMethod', 'Continuous');
% Create a ErrorRate Calculator System object. Account for the receive
% delay caused by the traceback length of the viterbi decoder.
hErrorCalc = comm.ErrorRate('ReceiveDelay', 48);
ber = zeros(3,1); % Store BER values
code = step(hConvEnc,msg); % Encode the data.
hChan.SignalPower = (code'*code)/length(code);
ncode = step(hChan,code); % Add noise.

% Quantize to prepare for soft-decision decoding.
qcode = quantiz(ncode,[0.001,.1,.3,.5,.7,.9,.999]);

tblen = 48; delay = tblen; % Traceback length
decoded = step(hVitDec,qcode); % Decode.

% Compute bit error rate.
ber = step(hErrorCalc, msg, decoded);
ratio = ber(1)
number = ber(2)
RandStream.setGlobalStream(prevStream);

Ниже приведен выход.

number =

     5


ratio =

    0.0013

Реализуйте декодирование с мягким решением с использованием Simulink.  Этот пример создает сверточный код скорости 1/2. Он использует квантователь и блок Viterbi Decoder, чтобы выполнить декодирование с мягким решением. Чтобы открыть модель, введите doc_softdecision в командной строке MATLAB. Описание модели см. в разделе Обзор симуляции.

Определение сверточного кода

Сверточный энкодер с прямой связью в этом примере показан ниже.

Длина ограничения энкодера является скаляром, поскольку энкодер имеет один вход. Значение длины ограничения является количеством бит, сохраненных в регистре сдвига, включая текущий вход. Регистров памяти шесть, а текущий вход составляет один бит. Таким образом, длина ограничения кода составляет 7.

Генератор кода является матрицей 1 на 2 восьмеричных чисел, потому что энкодер имеет один вход и два выхода. Первый элемент в матрице указывает, какие входные значения вносят вклад в первый выход, а второй элемент в матрице указывает, какие входные значения вносят вклад во второй выход.

Для примера первый выход в схеме энкодера является суммой по модулю-2 крайнего правого и четырех крайних левых элементов в массиве входа значений схемы. Двоичное число с семью цифрами 1 111 001 захват эта информация, и эквивалентно октальному номеру 171. Таким образом, восьмеричное число 171 становится первой записью матрицы генератора кода. Здесь каждый триплет битов использует самый левый бит как самый значительный бит. Второй выход соответствует двоичному числу 1011011, которое эквивалентно октальному числу 133. Поэтому генератор кода является [171 133].

Параметр Trellis structure в блоке Convolutional Encoder сообщает блоку, какой код использовать при обработке данных. В этом случае, poly2trellis функция в Communications Toolbox преобразует длину ограничения и пару восьмеричных чисел в допустимую структуру шпалеры.

Хотя данные сообщения, поступающие в блок Сверточного Энкодера, являются скалярным битовым потоком, закодированные данные, покидающие блок, являются потоком двоичных векторов длины 2.

Отображение полученных данных

Полученные данные, то есть выход блока AWGN Channel, состоят из комплексных чисел, которые близки к -1 и 1. В порядок восстановления исходного двоичного сообщения приемника часть модели должна декодировать сверточный код. Блок Viterbi Decoder в этой модели ожидает, что его входные данные будут целыми числами от 0 до 7. Демодулятор, пользовательская подсистема в этой модели, преобразует полученные данные в формат, который блок Viterbi Decoder может правильно интерпретировать. Более конкретно, подсистема демодулятора

Комбинация этого отображения и блока Viterbi Decoder преобразования принятия решений отменяет модуляцию BPSK, которую блок BPSK Modulator Baseband выполняет на передающей стороне этой модели. Чтобы изучить подсистему демодулятора более подробно, дважды щелкните значок, помеченный как Soft-Output BPSK Demodulator.

Декодирование сверточного кода

После того, как полученные данные правильно сопоставлены с векторами length-2 с 3-битными значениями принятия решений, блок Viterbi Decoder декодирует его. Блок использует алгоритм мягкого решения с 2³ различные входные значения, потому что параметр Decision type Soft Decision и параметр Number of soft decision bits 3.

Интерпретация данных с мягким решением

Когда параметр Decision type установлен в Soft Decisionблок Viterbi Decoder требует входных значений от 0 до 2^b-1, где b - Number of soft decision bits параметр. Блок интерпретирует 0 как самое уверенное решение, что бит кодового слова является 0 и интерпретирует 2^b-1 как самое уверенное решение, что бит кодового слова равен 1. Значения, существующие между этими крайностями, представляют собой менее уверенные в себе решения. В следующей таблице перечислены интерпретации восьми возможных входных значений для этого примера.

Задержка отслеживания и декодирования

Глубина отслеживания влияет на задержку декодирования. Задержка декодирования является количеством нулевых символов, которые предшествуют первому декодированному символу на выходе.

Оценка глубины следа

Как общая оценка, типичное значение глубины следа приблизительно в два-три раза (ConstraintLength-1 )/( 1- coderate). Длина ограничения кода, ConstraintLength, равна (log2 (trellis. numStates) + 1). Значение coderate равно (K/ N) × (длина (PuncturePattern )/сумма (PuncturePattern).

K - количество входа символов, N - количество выхода символов, а PuncturePattern - вектор пунктирного шаблона.

Для примера, применение этой общей оценки, результатов в этих приблизительных глубинах следа.

Параметр Traceback depth в блоке Viterbi Decoder представляет длину задержки декодирования. Некоторые аппаратные реализации предлагают опции 48 и 96. Этот пример выбирает 48, потому что это ближе к оцененной цели для кода ½ скоростью с длиной ограничения 7.

Задержка в полученных данных

Параметр Receive delay блока Error Rate Calculation ненулевой, потому что заданный бит сообщения и соответствующий ему восстановленный бит разделены во времени ненулевым количеством времени симуляции. Параметр Receive delay сообщает блоку, какие элементы его входных сигналов сравнивать при проверке на ошибки.

В этом случае значение задержки приема равно значению глубины трассировки (48).

Сравнение результатов симуляции с теоретическими результатами

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

Разработайте Rate-2/3 энкодер с Feedforward с использованием MATLAB

В приведенном ниже примере используется энкодер скорости 2/3 с feedforward, изображенный на этой схеме. Сопроводительное описание объясняет, как определить параметр структуры шпалеры из схемы энкодера, а затем как выполнить кодирование с использованием этого энкодера.

Определение параметров кодирования.   convenc и vitdec функции могут реализовать этот код, если их параметры имеют соответствующие значения.

Длина ограничения энкодера является вектором длины 2, потому что энкодер имеет два входа. Элементы этого вектора указывают количество битов, сохраненных в каждом регистре сдвига, включая текущие входные биты. Подсчет пространств в памяти в каждом регистре сдвига на схеме и добавление единицы для входных входов тока приводит к ограничительной длине [5 4].

Чтобы определить параметр генератора кода как матрицу 2 на 3 восьмеричных чисел, используйте элемент в i-й строке и j-й столбец, чтобы указать, как i-й вход вносит вклад в j-й выход. Для примера, чтобы вычислить элемент во второй строке и третьем столбце, крайний левый и два крайних правых элемента во втором регистре сдвига схемы подаются в сумму, которая формирует третий выход. Захватите эту информацию как двоичное число 1011, которое эквивалентно восьмеричному числу 13. Полное значение матрицы генератора кода является [23 35 0; 0 5 13].

Чтобы использовать ограничения длины и параметров генератора кода в convenc и vitdec функций, использовать poly2trellis функция для преобразования этих параметров в решетчатую структуру. Команда для этого приведена ниже.

trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Define trellis.

Использование энкодера.  Ниже представлен скрипт, который использует этот энкодер.

len = 1000;

msg = randi([0 1],2*len,1); % Random binary message of 2-bit symbols
trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Trellis
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(trel);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(trel, 'InputFormat', 'hard', ...
    'TracebackDepth', 34, 'TerminationMethod', 'Continuous');
% Create a ErrorRate Calculator System object. Since each symbol represents
% two bits, the receive delay for this object is twice the traceback length
% of the viterbi decoder.
hErrorCalc = comm.ErrorRate('ReceiveDelay', 68);
ber = zeros(3,1); % Store BER values
code = step(hConvEnc,msg); % Encode the message.
ncode = rem(code + randerr(3*len,1,[0 1;.96 .04]),2); % Add noise.
decoded = step(hVitDec, ncode); % Decode.
ber = step(hErrorCalc, msg, decoded);

convenc принимает вектор, содержащий 2-битные символы, и создает вектор, содержащий 3-битные символы, в то время как vitdec делает обратное. Также заметьте, что biterr игнорирует первые 68 элементов decoded. То есть задержка декодирования составляет 68, что является количеством бит на символ (2) восстановленного сообщения, умноженным на значение глубины отслеживания (34) в vitdec функция. Первые 68 элементов decoded 0, в то время как последующие элементы представляют декодированные сообщения.

Проектируйте скорость 2/3 Feedforward Энкодера с помощью Simulink

Этот пример использует сверточный энкодер со скоростью 2/3 с прямой связью, изображенный на следующем рисунке. Описание объясняет, как определить параметры блоков кодирования из схемы энкодера скорости 2/3 с feedforward. Этот пример также иллюстрирует использование блока Error Rate Calculation с задержкой приема.

Как определить параметры кодирования.  Блоки Convolutional Encoder и Viterbi Decoder могут реализовать этот код, если их параметры имеют соответствующие значения.

Длина ограничения энкодера является вектором длины 2, поскольку энкодер имеет два входа. Элементы этого вектора указывают количество битов, сохраненных в каждом регистре сдвига, включая текущие входные биты. Подсчет пространств в памяти в каждом регистре сдвига на схеме и добавление единицы для входных входов тока приводит к ограничительной длине [5 4].

Чтобы определить параметр генератора кода как матрицу 2 на 3 восьмеричных чисел, используйте элемент в i-й строке и j-й столбец, чтобы указать, как i-й вход вносит вклад в j-й выход. Для примера, чтобы вычислить элемент во второй строке и третьем столбце, заметьте, что самый левый и два крайних правых элемента во втором регистре сдвига схемы поступают в сумму, которая формирует третий выход. Захватите эту информацию как двоичное число 1011, которое эквивалентно восьмеричному числу 13. Полное значение матрицы генератора кода является [27 33 0; 0 5 13].

Чтобы использовать параметры длины ограничения и генератора кода в блоках Convolutional Encoder и Viterbi Decoder, используйте poly2trellis функция для преобразования этих параметров в решетчатую структуру.

Моделирование энкодера.  Следующая модель моделирует этот энкодер.

Чтобы открыть завершенную модель, введите doc_convcoding в командной строке MATLAB. Чтобы создать модель, соберите и сконфигурируйте эти блоки:

Соедините блоки как показано на предыдущем рисунке. На вкладке Simulation, в разделе Simulate, установите Stop time равным inf. Раздел Simulate появляется на нескольких вкладках.

Примечания к модели.  Вы можете отобразить размер матрицы сигналов в вашей модели. На вкладке Debug разверните Information Overlays. В Signals разделе выберите Signal Dimensions.

Энкодер принимает вектор-столбец 2 на 1 и производит вектор-столбец 3 на 1, в то время как декодер делает обратное. Параметр Samples per frame в блоке Bernoulli Binary Generator равен 2, потому что блок должен сгенерировать слово сообщения длины 2.

Параметр Receive delay в блоке Вычисления Частоты Ошибок является 68, который является длиной вектора (2) восстановленного сообщения, умноженной на Traceback depth значение (34) в блоке Декодера Витерби. Если вы исследуете переданные и принятые сигналы как матрицы в рабочем пространстве MATLAB, то видите, что первые 34 строки восстановленного сообщения состоят из нулей, в то время как последующие строки являются декодированными сообщениями. Таким образом, задержка в принимаемом сигнале составляет 34 вектора длины 2 или 68 выборки.

Выполнение модели производит отображаемый вывод, состоящий из трех чисел: вероятность ошибки, общее количество ошибок и общее количество сравнений, которые блок Вычисления Частоты Ошибок делает во время симуляции. (Первые два числа варьируются в зависимости от значений Initial seed в блоках Bernoulli Binary Generator и Binary Symmetric Channel.) Симуляция останавливается после возникновения 100 ошибок, потому что Target number of errors установлено на 100 в блоке Error Rate Calculation. Вероятность ошибок намного меньше 0.02, Error probability в блоке «Двоичный симметричный канал».

Пункция сверточного кода с помощью MATLAB

Этот пример обрабатывает проколотый сверточный код. Он начинается с генерации 30 000 случайных бит и кодирования их с помощью сверточного энкодера скорости 3/4 с шаблоном прокола [1 1 1 0 0 1]. Получившийся вектор содержит 40 000 биты, которые отображаются на значения -1 и 1 для передачи. Проколотый код, punctcode, проходит через аддитивный канал белого Гауссова шума. Тогда vitdec декодирует зашумленный вектор, используя 'unquant' тип решения.

Наконец, в примере вычисляется вероятность битовой ошибки и количество битовых ошибок.

len = 30000; msg = randi([0 1], len, 1); % Random data
t = poly2trellis(7, [133 171]); % Define trellis.
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(t, ...
    'PuncturePatternSource', 'Property', ...
    'PuncturePattern', [1;1;1;0;0;1]);
% Create an AWGNChannel System object.
hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',...
  'SNR', 3);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Unquantized', ...
    'TracebackDepth', 96, 'TerminationMethod', 'Truncated', ...
    'PuncturePatternSource', 'Property', ...
    'PuncturePattern', [1;1;1;0;0;1]);
% Create a ErrorRate Calculator System object.
hErrorCalc = comm.ErrorRate;
berP = zeros(3,1); berPE = berP; % Store BER values
punctcode = step(hConvEnc,msg); % Length is (2*len)*2/3.
tcode = 1-2*punctcode; % Map "0" bit to 1 and "1" bit to -1
hChan.SignalPower = (tcode'*tcode)/length(tcode);
ncode = step(hChan,tcode); % Add noise.

% Decode the punctured code
decoded = step(hVitDec,ncode); % Decode.
berP = step(hErrorCalc, msg, decoded);% Bit error rate
% Erase the least reliable 100 symbols, then decode
release(hVitDec); reset(hErrorCalc)
hVitDec.ErasuresInputPort = true;
[dummy idx] = sort(abs(ncode));
erasures =  zeros(size(ncode)); erasures(idx(1:100)) = 1;
decoded = step(hVitDec,ncode, erasures); % Decode.
berPE = step(hErrorCalc, msg, decoded);% Bit error rate

fprintf('Number of errors with puncturing: %d\n', berP(2))
fprintf('Number of errors with puncturing and erasures: %d\n', berPE(2))

Реализуйте систематический энкодер с обратной связью с помощью Simulink

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

Чтобы реализовать этот энкодер, установите параметр Trellis structure в блоке Convolutional Encoder равным poly2trellis(5, [37 33], 37). Эта настройка соответствует

Полином обратной связи представлен двоичным вектором [1 1 1 1 1], соответствующим верхней строке двоичных цифр. Эти цифры указывают на соединения между выходами регистров и сумматором. Начальный 1 соответствует вход биту. Восьмеричное представление двоичного числа 11111 составляет 37.

Чтобы реализовать систематический код, установите первый полином генератора таким же, как полином обратной связи в параметре Trellis structure блока Convolutional Encoder. В этом примере оба полинома имеют октальное представление 37.

Полином второго генератора представлен двоичным вектором [1 1 0 1 1], соответствующим нижней строке двоичных цифр. Восьмеричное число, соответствующее двоичному числу 11011, равно 33.

Для получения дополнительной информации об установке параметров маски для блока Convolutional Encoder, смотрите Полином Описание сверточного кода.

Декодирование с мягким решением

Этот пример создает сверточный код скорости 1/2. Он использует квантователь и блок Viterbi Decoder, чтобы выполнить декодирование с мягким решением. Это описание охватывает следующие темы:

• Обзор симуляции

• Определение сверточного кода

• Отображение полученных данных

• Декодирование сверточного кода

• Задержка в полученных данных

• Сравнение результатов симуляции с теоретическими результатами

Обзор симуляции.  Модель представлена на следующем рисунке. Чтобы открыть модель, введите doc_softdecision в командной строке MATLAB. Эта симуляция создаёт сигнал случайного двоичного сообщения, кодирует сообщение в сверточный код, модулирует код с помощью метода двоичной манипуляции фазы сдвига (BPSK) и добавляет белый Гауссов шум к модулированным данным в порядок для симуляции шумного канала. Затем симуляция подготавливает принятые данные для блока декодирования и декодирует. Наконец, симуляция сравнивает декодированную информацию с исходным сигналом сообщения в порядок для вычисления частоты битовой ошибки. Сверточный энкодер сконфигурирован как кодер скорости 1/2. На каждые 2 бита энкодер добавляет еще 2 избыточных бита. Чтобы учесть это и добавить правильное количество шума, параметр Eb/No (dB) блока AWGN в эффект раз уменьшается путем вычитания 10 * log10 (2). Симуляция заканчивается после обработки 100 битовых ошибок или 10⁷ биты сообщений, в зависимости от того, что наступит раньше.

Определение сверточного кода.  Сверточный энкодер с прямой связью в этом примере показан ниже.

Длина ограничения энкодера является скаляром, поскольку энкодер имеет один вход. Значение длины ограничения является количеством бит, сохраненных в регистре сдвига, включая текущий вход. Регистров памяти шесть, а текущий вход составляет один бит. Таким образом, длина ограничения кода составляет 7.

Генератор кода является матрицей 1 на 2 восьмеричных чисел, потому что энкодер имеет один вход и два выхода. Первый элемент в матрице указывает, какие входные значения вносят вклад в первый выход, а второй элемент в матрице указывает, какие входные значения вносят вклад во второй выход.

Для примера первый выход в схеме энкодера является суммой по модулю-2 крайнего правого и четырех крайних левых элементов в массиве входа значений схемы. Двоичное число с семью цифрами 1 111 001 захват эта информация, и эквивалентно октальному номеру 171. Таким образом, восьмеричное число 171 становится первой записью матрицы генератора кода. Здесь каждый триплет битов использует самый левый бит как самый значительный бит. Второй выход соответствует двоичному числу 1011011, которое эквивалентно октальному числу 133. Поэтому генератор кода является [171 133].

Параметр Trellis structure в блоке Convolutional Encoder сообщает блоку, какой код использовать при обработке данных. В этом случае, poly2trellis функция в Communications Toolbox преобразует длину ограничения и пару восьмеричных чисел в допустимую структуру шпалеры.

Хотя данные сообщения, поступающие в блок Сверточного Энкодера, являются скалярным битовым потоком, закодированные данные, покидающие блок, являются потоком двоичных векторов длины 2.

Отображение полученных данных.  Полученные данные, то есть выход блока AWGN Channel, состоят из комплексных чисел, которые близки к -1 и 1. В порядок восстановления исходного двоичного сообщения приемника часть модели должна декодировать сверточный код. Блок Viterbi Decoder в этой модели ожидает, что его входные данные будут целыми числами от 0 до 7. Демодулятор, пользовательская подсистема в этой модели, преобразует полученные данные в формат, который блок Viterbi Decoder может правильно интерпретировать. Более конкретно, подсистема демодулятора

Комбинация этого отображения и блока Viterbi Decoder преобразования принятия решений отменяет модуляцию BPSK, которую блок BPSK Modulator Baseband выполняет на передающей стороне этой модели. Чтобы изучить подсистему демодулятора более подробно, дважды щелкните значок, помеченный как Soft-Output BPSK Demodulator.

Декодирование сверточного кода.  После того, как полученные данные правильно сопоставлены с векторами length-2 с 3-битными значениями принятия решений, блок Viterbi Decoder декодирует его. Блок использует алгоритм мягкого решения с 2³ различные входные значения, потому что параметр Decision type Soft Decision и параметр Number of soft decision bits 3.

Интерпретация данных с мягким решением

Когда параметр Decision type установлен в Soft Decisionблок Viterbi Decoder требует входных значений от 0 до 2^b-1, где b - Number of soft decision bits параметр. Блок интерпретирует 0 как самое уверенное решение, что бит кодового слова является 0 и интерпретирует 2^b-1 как самое уверенное решение, что бит кодового слова равен 1. Значения, существующие между этими крайностями, представляют собой менее уверенные в себе решения. В следующей таблице перечислены интерпретации восьми возможных входных значений для этого примера.

Задержка отслеживания и декодирования

Параметр Traceback depth в блоке Viterbi Decoder представляет длину задержки декодирования. Типичные значения глубины обратного отслеживания примерно в пять или шесть раз превышают длину ограничения, которая в этом примере составляет 35 или 42. Однако некоторые аппаратные реализации предлагают опции 48 и 96. Этот пример выбирает 48, потому что это ближе к целям (35 и 42), чем 96.

Задержка в полученных данных.  Параметр Receive delay блока Error Rate Calculation ненулевой, потому что заданный бит сообщения и соответствующий ему восстановленный бит разделены во времени ненулевым количеством времени симуляции. Параметр Receive delay сообщает блоку, какие элементы его входных сигналов сравнивать при проверке на ошибки.

В этом случае значение задержки приема равно значению глубины трассировки (48).

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

Вычисление теоретических границ для частоты битовой ошибки

Чтобы вычислить теоретические границы для частоты битовой ошибки Pb сверточного кода в этой модели, можно использовать эту оценку на основе декодирования без квантования решения:

В этой оценке cd является суммой битовых ошибок для событий ошибки расстояния d, и f является свободным расстоянием кода. Величина Pd является вероятностью парной ошибки, заданная как

где R - скорость кода 1/2, и erfc - дополнительная функция ошибки MATLAB, заданная как

Значения коэффициентов cd и свободного расстояния f находятся в опубликованных статьях, таких как «Сверточные коды с оптимальным спектром расстояний» [3]. Свободное расстояние для этого кода f  = 10.

Следующие команды вычисляют значения Pb для Eb/N0 значений в области значений от 1 до 4 с шагами 0,5:

EbNoVec = [1:0.5:4.0];
R = 1/2;
% Errs is the vector of sums of bit errors for
% error events at distance d, for d from 10 to 29.
Errs = [36 0 211 0 1404 0 11633 0 77433 0 502690 0,...
        3322763 0 21292910 0 134365911 0 843425871 0]; 
% P is the matrix of pairwise error probilities, for
% Eb/No values in EbNoVec and d from 10 to 29.
P = zeros(20,7); % Initialize.
for d = 10:29
   P(d-9,:) = (1/2)*erfc(sqrt(d*R*10.^(EbNoVec/10)));
end
% Bounds is the vector of upper bounds for the bit error
% rate, for Eb/No values in EbNoVec.
Bounds = Errs*P;

Симуляция нескольких раз для сбора частот битовых ошибок

Можно эффективно варьировать параметры симуляции при помощи sim (Simulink), чтобы запустить симуляцию из командной строки MATLAB. Например, следующий код вычисляет частоту битовой ошибки при соотношениях энергия-шум в битах в диапазоне от 1 дБ до 4 дБ с шагами 0,5 дБ. Он собирает все частоты битовой ошибки из этих симуляций в матрице BERVec. Он также строит график частот битовой ошибки в окне рисунка вместе с теоретическими границами, вычисленными в предыдущем фрагменте кода.

% Plot theoretical bounds and set up figure.
figure;
semilogy(EbNoVec,Bounds,'bo',1,NaN,'r*');
xlabel('Eb/No (dB)'); ylabel('Bit Error Rate');
title('Bit Error Rate (BER)');
legend('Theoretical bound on BER','Actual BER');
axis([1 4 1e-5 1]);
hold on;

BERVec = [];
% Make the noise level variable.
set_param('doc_softdecision/AWGN Channel',...
    'EsNodB','EbNodB+10*log10(1/2)');
% Simulate multiple times.
for n = 1:length(EbNoVec)
    EbNodB = EbNoVec(n);
    sim('doc_softdecision',5000000);
    BERVec(n,:) = BER_Data;
    semilogy(EbNoVec(n),BERVec(n,1),'r*'); % Plot point.
    drawnow;
end
hold off;

График частоты битовой ошибки относительно отношения сигнал/шум следующий. Местоположения ваших фактических точек BER могут варьироваться, потому что симуляция включает случайные числа.

Настройка кодировки с использованием энкодеров обратной связи

Этот пример демонстрирует Tailbiting кодирование с использованием энкодеров обратной связи. Для энкодеров обратной связи конечное состояние зависит от всего блока данных. Чтобы выполнить хитрость, необходимо вычислить для данного информационного вектора (из N бит), начальное состояние, которое приводит к тому же конечному состоянию после кодирования блока данных.

Это достигается в два этапа:

Теоретическое вычисление начального состояния см. в [8] _X0 из _XN ^[zs] использование формулировки в пространстве состояний. Это одноразовое вычисление, которое зависит от длины блока и на практике может быть реализовано как интерполяционная таблица. Здесь мы определяем эту таблицу отображения, моделируя все возможные значения для выбранных решетки и длины блока.

Чтобы открыть модель, введите doc_mtailbiting_wfeedback в командной строке MATLAB.

function mapStValues = getMapping(blkLen, trellis)
% The function returns the mapping value for the given block
length and trellis to be used for determining the initial
state from the zero-state response.

% All possible combinations of the mappings
mapStValuesTab = perms(0:trellis.numStates-1);

% Loop over all the combinations of the mapping entries:
for i = 1:length(mapStValuesTab)
mapStValues = mapStValuesTab(i,:);

% Model parameterized for the Block length
sim('mtailbiting_wfeedback');

% Check the boundary condition for each run
% if ending and starting states match, choose that mapping set
if unique(out)==0
        return
    end
end

Выбор возвращенного mapStValues для параметра Table data Direct Lookup Table (n-D) блок в подсистеме Lookup будет выполнять пользовательскую кодировку для выбранных длины блока и шпалеры.

Выбранная библиография для сверточного кодирования

Представление слов для линейных блочных кодов

Циклическая, Hamming и типовая функциональность линейного блочного кода в этом продукте предлагают вам несколько способов организовать биты в сообщениях или кодовых словах. В следующих разделах описываются доступные форматы:

• Используйте MATLAB для создания сообщений и кодовых слов в двоичном векторном формате

• Используйте MATLAB для создания сообщений и кодовых слов в двоичном формате матрицы

• Используйте MATLAB для создания сообщений и кодовых слов в десятичном векторном формате

Чтобы узнать, как представлять слова для кодов BCH или Рида-Соломона, смотрите Представление слов для кодов BCH или Представление слов для кодов Рида-Соломона.

Используйте MATLAB для создания сообщений и кодовых слов в двоичном формате Вектора.  Ваши сообщения и кодовые слова могут принимать форму векторов, содержащих 0s и 1s. Например, сообщения и коды могут выглядеть следующим образом msg и code в линиях ниже.

n = 6; k = 4; % Set codeword length and message length
% for a [6,4] code.
msg = [1 0 0 1 1 0 1 0 1 0 1 1]'; % Message is a binary column.
code = encode(msg,n,k,'cyclic'); % Code will be a binary column.
msg'
code'

Ниже приведен выход.

ans =

  Columns 1 through 5

      1            0            0            1            1

  Columns 6 through 10

      0            1            0            1            0

  Columns 11 through 12

      1            1


ans =

  Columns 1 through 5

      1            1            1            0            0

  Columns 6 through 10

      1            0            0            1            0

  Columns 11 through 15

      1            0            0            1            1

  Columns 16 through 18

      0            1            1      

В этом примере msg состоит из 12 записей, которые интерпретируются как три 4-значные (потому что k = 4) сообщения. Получившийся вектор code содержит три 6-значные (потому что n = 6) кодовые слова, которые объединены для формирования вектора длины 18. Биты четности находятся в начале каждого кодового слова.

Используйте MATLAB для создания сообщений и кодовых слов в формате двоичной матрицы.  Можно организовать информацию о кодировании так, чтобы подчеркнуть группировку цифр в сообщения и кодовые слова. Если вы используете этот подход, каждое сообщение или кодовое слово занимает строку в двоичной матрице. Приведенный ниже пример иллюстрирует этот подход путем перечисления каждого 4-битного сообщения в отдельной строке msg и каждое 6-битное кодовое слово в отдельной строке code.

n = 6; k = 4; % Set codeword length and message length.
msg = [1 0 0 1; 1 0 1 0; 1 0 1 1]; % Message is a binary matrix.
code = encode(msg,n,k,'cyclic'); % Code will be a binary matrix.
msg
code

Ниже приведен выход.

msg =

     1     0     0     1
     1     0     1     0
     1     0     1     1


code =

     1     1     1     0     0     1
     0     0     1     0     1     0
     0     1     1     0     1     1

Используйте MATLAB для создания сообщений и кодовых слов в десятичном векторном формате.  Ваши сообщения и кодовые слова могут принимать форму векторов, содержащих целые числа. Каждый элемент вектора задает десятичное представление бит в одном сообщении или одном кодовом слове.

Синтаксис файла encode команда должна явно упомянуть десятичный формат, как в примере ниже. Заметьте, что /decimal добавляется к четвертому аргументу в encode команда.

n = 6; k = 4; % Set codeword length and message length.
msg = [9;5;13]; % Message is a decimal column vector.
% Code will be a decimal vector.
code = encode(msg,n,k,'cyclic/decimal')

Ниже приведен выход.

code =

    39
    20
    54

Сконфигурируйте параметры для линейных блочных кодов

В этом подразделе описываются элементы, которые могут понадобиться для обработки [n, k] циклических, Hamming и типовых линейных блочных кодов. В приведенной ниже таблице перечислены элементы и методы кодирования, для которых они наиболее актуальны .

Матрица генератора.  Процесс кодирования сообщения в [n, k] линейный блочный код определяется k-на-n матрицей генератора G. В частности, вектор v сообщения 1 на k кодируется в вектор vG кодового слова 1 на n. Если G имеет вид [_Ik P] или [ P _Ik], где P является некоторой k-by- (n-k) матрицей, а Ik является k-by-k тождеств матрицей, то G называется стандартной формой. (Некоторые авторы, например, Clark and Cain [2], используют первую стандартную форму, другие, например, Lin и Costello [3], используют вторую.) Большинство функций в этом тулбоксе предполагают, что матрица генератора находится в стандартной форме, когда вы используете ее как входной параметр.

Некоторые примеры матриц генератора находятся в следующем разделе, Матрица проверки четности.

Матрица проверки четности.  Для декодирования [n, k] линейного блочного кода требуется (n-k) -на-n матрица проверки четности H. Это удовлетворяет GH^tr = 0 (mod 2), где H^tr обозначает матрицу транспонирования H, G является матрицей генератора кода, и эта нулевая матрица является k-by- (n-k). Если G = [_Ik P], то H = [-P^tr _In-k]. Большинство функций в этом продукте предполагают, что матрица проверки четности находится в стандартной форме, когда вы используете ее как входной параметр.

В таблице ниже приведены стандартные формы генератора и матриц проверки четности для [n, k] двоичного линейного блочного кода .

_Ik - тождества матрица размера k и ' символ указывает на транспонирование матрицы. (Для двоичных кодов знаки минус в форме проверки четности, перечисленной выше, нерелевантны; то есть -1 = 1 в двоичном поле.)

Примеры

В приведенной ниже команде parmat является матрицей с проверкой четности и genmat - матрица генератора для кода Хемминга, в которой [n, k ] = [2³-1, n-3] = [7,4]. genmat имеет стандартную форму [P _Ik].

[parmat,genmat] = hammgen(3)
parmat =

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat =

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

Следующий пример находит матрицы проверки четности и генератора для циклического кода [7,3]. cyclpoly функция упоминается ниже в Полином.

genpoly = cyclpoly(7,3);
[parmat,genmat] = cyclgen(7,genpoly)
parmat =

     1     0     0     0     1     1     0
     0     1     0     0     0     1     1
     0     0     1     0     1     1     1
     0     0     0     1     1     0     1

genmat =

     1     0     1     1     1     0     0
     1     1     1     0     0     1     0
     0     1     1     1     0     0     1

Приведенный ниже пример преобразует матрицу генератора для линейного блочного кода [5,3] в соответствующую матрицу проверки четности.

genmat = [1 0 0 1 0; 0 1 0 1 1; 0 0 1 0 1];
parmat = gen2par(genmat)

parmat =

     1     1     0     1     0
     0     1     1     0     1

Та же функция gen2par может также преобразовать матрицу проверки четности в матрицу генератора.

Полином генератора.  Циклические коды имеют алгебраические свойства, которые позволяют полиному полностью определить процесс кодирования. Этот так называемый полином генератора является степени- (n-k) делителем многочлена xⁿ-1. Ван Линт [5] объясняет, как полином генератора определяет циклический код.

cyclpoly функция производит полиномы генератора для циклических кодов. cyclpoly представляет полином генератора, используя вектор-строку, который приводит коэффициенты полинома в порядке возрастания степени переменной. Для примера используйте команду

genpoly = cyclpoly(7,3)

genpoly =

     1     0     1     1     1

находит, что один действительный полином генератора для [7,3] циклического кода равен 1 + x² + x³ + x⁴.

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

Этот тулбокс представляет таблицу декодирования как матрицу с n столбцы и 2^(n-k) строки. Каждая строка задает вектор коррекции для одного полученного вектора кодового слова. Таблица декодирования Hamming имеет n+ 1 строка. syndtable функция генерирует таблицу декодирования для заданной матрицы проверки четности.

Использование таблицы декодирования в MATLAB

Скрипт ниже показывает, как использовать таблицу декодирования Hamming, чтобы исправить ошибку в полученном сообщении. hammgen функция создает матрицу проверки четности, в то время как syndtable функция создает таблицу декодирования. Транспонирование матрицы проверки четности умножается слева на принятое кодовое слово, приводя к синдрому. Таблица декодирования помогает определить вектор коррекции. Исправленное кодовое слово является суммой (по модулю 2) вектора коррекции и принятого кодового слова.

% Use a [7,4] Hamming code.
m = 3; n = 2^m-1; k = n-m;
parmat = hammgen(m); % Produce parity-check matrix.
trt = syndtable(parmat); % Produce decoding table.
recd = [1 0 0 1 1 1 1] % Suppose this is the received vector.
syndrome = rem(recd * parmat',2);
syndrome_de = bi2de(syndrome,'left-msb'); % Convert to decimal.
disp(['Syndrome = ',num2str(syndrome_de),...
      ' (decimal), ',num2str(syndrome),' (binary)'])
corrvect = trt(1+syndrome_de,:) % Correction vector
% Now compute the corrected codeword.
correctedcode = rem(corrvect+recd,2)

Ниже приведен выход.

recd =

     1     0     0     1     1     1     1

Syndrome = 3 (decimal), 0  1  1 (binary)

corrvect =

     0     0     0     0     1     0     0


correctedcode =

     1     0     0     1     0     1     1

Создайте и декодируйте линейные блочные коды

Функции для кодирования и декодирования циклических, Хэмминговых и типовых линейных блочных кодов encode и decode. В этом разделе рассматривается, как использовать эти функции для создания и декодирования типовых линейных блочных кодов, циклических кодов и Hamming-кодов.

Типовые линейные коды блоков.  Для кодирования сообщения с помощью типового линейного блочного кода требуется матрица генератора. Если у вас есть определенные переменные msg, n, k, и genmat, любую из команд

code = encode(msg,n,k,'linear',genmat);
code = encode(msg,n,k,'linear/decimal',genmat);

кодирует информацию в msg использование [n, k] кодируйте, что матрица генератора genmat определяет. The /decimal опция, подходящая при 2^n и 2^k не очень большие, указывает, что msg содержит неотрицательные десятичные целые числа, а не их двоичные представления. См. «Представление слов для линейных блочных кодов» или страницу с описанием для encode для описания форматов msg и code.

Для декодирования кода требуется матрица генератора и, возможно, таблица декодирования. Если у вас есть определенные переменные code, n, k, genmat, и, возможно, также trt, затем команды

newmsg = decode(code,n,k,'linear',genmat);
newmsg = decode(code,n,k,'linear/decimal',genmat);
newmsg = decode(code,n,k,'linear',genmat,trt);
newmsg = decode(code,n,k,'linear/decimal',genmat,trt);

декодируйте информацию в code, с использованием [n, k] кодируйте, что матрица генератора genmat определяет. decode также исправляет ошибки согласно инструкциям в таблице декодирования, которые trt представляет собой.

Пример: Типовое линейное блочное кодирование

Приведенный ниже пример кодирует сообщение, искусственно добавляет некоторый шум, декодирует шумный код и отслеживает ошибки, которые декодер обнаруживает на этом пути. Поскольку таблица декодирования содержит только нули, декодер не исправляет никаких ошибок.

n = 4; k = 2;
genmat = [[1 1; 1 0], eye(2)]; % Generator matrix
msg = [0 1; 0 0; 1 0]; % Three messages, two bits each
% Create three codewords, four bits each.
code = encode(msg,n,k,'linear',genmat);
noisycode = rem(code + randerr(3,4,[0 1;.7 .3]),2); % Add noise.
trt = zeros(2^(n-k),n);  % No correction of errors
% Decode, keeping track of all detected errors.
[newmsg,err] = decode(noisycode,n,k,'linear',genmat,trt);
err_words = find(err~=0) % Find out which words had errors.

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

err_words =

     1
     2

Циклические коды.  Циклический код является линейным блочным кодом со свойством, что циклические сдвиги кодового слова (выраженные как серия бит) также являются кодовыми словами. Альтернативная характеристика циклических кодов основана на его полиноме генератора, как упомянуто в Generator Polynomial и обсуждается в [5].

Для кодирования сообщения с помощью циклического кода требуется полином генератора. Если у вас есть определенные переменные msg, n, k, и genpoly, затем любую из команд

code = encode(msg,n,k,'cyclic',genpoly);
code = encode(msg,n,k,'cyclic/decimal',genpoly);

кодирует информацию в msg использование [n, k] код, определяемый полиномом генератора genpoly. genpoly является необязательным аргументом для encode. Полином генератора по умолчанию является cyclpoly(n,k). The /decimal опция, подходящая при 2^n и 2^k не очень большие, указывает, что msg содержит неотрицательные десятичные целые числа, а не их двоичные представления. См. «Представление слов для линейных блочных кодов» или страницу с описанием для encode для описания форматов msg и code.

Для декодирования кода требуется полином генератора и, возможно, таблица декодирования. Если у вас есть определенные переменные code, n, k, genpoly, и trt, затем команды

newmsg = decode(code,n,k,'cyclic',genpoly);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly);
newmsg = decode(code,n,k,'cyclic',genpoly,trt);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly,trt);

декодируйте информацию в code, с использованием [n, k] кодируйте, что матрица генератора genmat определяет. decode также исправляет ошибки согласно инструкциям в таблице декодирования, которые trt представляет собой. genpoly является необязательным аргументом в первых двух синтаксисах выше. Полином генератора по умолчанию является cyclpoly(n,k).

Пример

Можно изменить пример в Типовых Линейных Блочных Кодах так, чтобы он использовал метод циклического кодирования, вместо линейного блочного кода с матрицей генератора genmat. Внесите следующие изменения:

Другой пример кодирования и декодирования циклического кода находится на странице с описанием для encode.

Коды Хемминга.  Страницы с описанием для encode и decode содержат примеры кодирования и декодирования кодов Хемминга. Кроме того, раздел «Таблица декодирования» иллюстрирует коррекцию ошибок в коде Хемминга.

Создайте Код Хемминга в двоичном формате с помощью Simulink

Этот пример показывает очень просто, как использовать энкодер и декодер. Он иллюстрирует соответствующие длины вектора кода и сигналов сообщения для блоков кодирования. Поскольку блок Error Rate Calculation принимает только скаляры или основанные на кадрах векторы-столбцы в качестве переданных и принятых сигналов, этот пример использует основанные на кадрах векторы-столбцы на всем протяжении. (Таким образом, он избегает необходимости изменять атрибуты сигнала с помощью блока, такого как Convert 1-D to 2-D.)

Откройте эту модель путем ввода doc_hamming в командной строке MATLAB. Чтобы создать модель, соберите и сконфигурируйте эти блоки:

Соедините блоки как на предыдущем рисунке. Вы можете отобразить длину вектора сигналов в своей модели. На вкладке Debug разверните Information Overlays. В Signals разделе выберите Signal Dimensions. После обновления схемы, при необходимости, нажмите Ctrl+D, чтобы скомпилировать модель и проверить статистику ошибок.

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

Уменьшите вероятность ошибок, используя код

В этом разделе описывается, как уменьшить вероятность ошибок путем добавления кода исправления ошибок. Этот рисунок показывает модель, которая использует код Хемминга.

Чтобы открыть полную версию модели, введите doc_hamming в подсказку MATLAB.

Создание модели кода Хемминга

Можно создать модель кода Хемминга, выполнив следующие шаги:

Модель теперь должна напоминать этот рисунок.

Использование блоков Энкодер и Decoder

Блок Hamming Encoder кодирует данные перед их отправкой через канал. Кодом по умолчанию является код [7,4] Hamming, который кодирует слова сообщения длины 4 в кодовые слова длины 7. В результате блок преобразует системы координат 4 размера в системы координат 7 размера. Код может исправить одну ошибку в каждом переданном кодовом слове.

Для кода [n, k] вход блока Hamming Encoder должен состоять из векторов размера k. В этом примере k = 4.

Блок Hamming Decoder декодирует данные после того, как они передаются через канал. Если в кодовом слове каналом создается не более одной ошибки, блок декодирует слово правильно. Однако, если происходит несколько ошибок, Hamming Decoder блок может декодироваться неправильно.

Дополнительные сведения о функциях блочного кодирования см. в разделе «Блочные коды».

Установка параметров в модели кода Хемминга

Дважды кликните блок Bernoulli Binary Generator и внесите следующие изменения в настройки параметра в диалоговом окне блока, как показано на следующем рисунке:

Маркировка дисплейного блока

Вы можете изменить метку, которая появляется под блоком, чтобы сделать его более информативным. Например, чтобы изменить метку под блоком Display на 'Error Rate Display'сначала выберите метку с помощью мыши. Это приводит к появлению рамки вокруг текста. Введите изменения текста в поле.

Запуск модели кода Хемминга

Чтобы запустить модель, выберите Simulation > Run. Модель заканчивается после того, как произойдет 100 ошибок. Вероятность ошибки, отображаемая в верхнем окне блока Отображения, составляет приблизительно 0,001. Вы получаете несколько другие результаты, если вы изменяете параметры Initial seed в модели или запускаете симуляцию в течение другого периода времени.

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

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

Чтобы получить более низкую частоту ошибок для той же вероятности ошибки, попробуйте использовать код Хемминга с большими параметрами. Для этого измените параметры Codeword length и Message length в диалоговых окнах Hamming Encoder и Hamming Decoder блоков. Вы также должны внести соответствующие изменения в параметры блока Bernoulli Binary Generator и блока Binary Symmetric Channel.

Отображение форматов кадра

Можно отобразить размеры систем координат данных в различных частях модели. На вкладке Debug разверните Information Overlays. В Signals разделе выберите Signal Dimensions. Линия, выходящая из блока Bernoulli Binary Generator, маркируется [4x1], что указывает на то, что его выход состоит из векторов-столбцов размера 4. Поскольку блок Hamming Encoder использует код [7,4], он преобразует системы координат размера 4 в системы координат размера 7, поэтому его выход помечается [7x1].

Добавление возможностей к модели

Чтобы отобразить ошибки канала, произведенные блоком Binary Symmetric Channel, добавьте блок Scope к модели. Это хороший способ увидеть, правильно ли работает ваша модель. Пример, показанный на следующем рисунке, показывает, где вставить Scope блок в модель.

Чтобы создать эту модель из модели, показанной на рисунке Уменьшите Частоту Ошибок Используя Код, выполните следующие шаги:

Установка параметров в расширенной модели

Внесите следующие изменения в параметры для блоков, которые вы добавили в модель.

Наблюдение ошибок канала с возможности

Когда вы запускаете модель, возможности отображают данные об ошибке. В конце каждого 5000 временных шагов возможности как показано на этом рисунке. Область возможностей очищает отображаемые данные и отображает следующие 5000 точек данных.

Верхняя область показывает ошибки канала, сгенерированные блоком Binary Symmetric Channel. Более низкие возможности показывают ошибки, которые не исправлены кодированием канала.

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

Отдельные ошибки можно увидеть путем изменения масштаба области возможностей. Сначала нажмите кнопку среднего лупы в верхней левой части Scope окна. Затем щелкните одну из линий нижних возможностей. Это увеличивает изображение по горизонтали на линии. Продолжайте клики по линиям в нижних возможностях, пока горизонтальная шкала не станет достаточно хорошим, чтобы обнаружить отдельные ошибки. Типичный пример того, что вы можете увидеть, показан на рисунке ниже.

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

Когда вы закончите наблюдать ошибки, выберите Simulation > Stop.

Экспорт данных в MATLAB объясняет, как отправить данные об ошибке в рабочее пространство MATLAB для более подробного анализа.

Представление слов для кодов BCH

Сообщение для [n, k] Код BCH должен быть k-столбец двоичный массив поля Галуа. Код, который соответствует этому сообщению, является n-столбец двоичный массив поля Галуа. Каждая строка этих массивов полей Галуа представляет одно слово.

Приведенный ниже пример иллюстрирует, как представлять слова для кода [15, 11] BCH.

msg = [1 0 0 1 0; 1 0 1 1 1]; % Messages in a Galois array
obj = comm.BCHEncoder;
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
cbch = [c1 c2].'

Это выход

  Columns 1 through 5

      1            0            0            1            0
      1            0            1            1            1

  Columns 6 through 10

      0            0            1            1            1
      0            0            0            0            1

  Columns 11 through 15

      1            0            1            0            1
      0            1            0            0            1  

Параметры для кодов BCH

В кодах BCH используются специальные значения n и k:

Создание и декодирование кодов BCH

The BCH Encoder и BCH Decoder Системные объекты создают и декодируют коды BCH, используя данные, описанные в Represent Words для кодов BCH и параметров для кодов BCH.

Темы:

• Пример: Синтаксисы кодирования BCH

• Обнаружение и исправление ошибок в коде BCH с помощью MATLAB

Пример: Синтаксис кодирования BCH.  Приведенный ниже пример иллюстрирует, как кодировать и декодировать данные с помощью кода [15, 5] BCH.

n = 15; k = 5; % Codeword length and message length
msg = randi([0 1],4*k,1); % Four random binary messages

% Simplest syntax for encoding
enc = comm.BCHEncoder(n,k);
dec = comm.BCHDecoder(n,k);
c1 = step(enc,msg); % BCH encoding
d1 = step(dec,c1); % BCH decoding

% Check that the decoding worked correctly.
chk = isequal(d1,msg)

% The following code shows how to perform the encoding and decoding
% operations if one chooses to prepend the parity symbols.

% Steps for converting encoded data with appended parity symbols
% to encoded data with prepended parity symbols
c11 = reshape(c1, n, []);
c12 = circshift(c11,n-k);
c1_prepend = c12(:); % BCH encoded data with prepended parity symbols

% Steps for converting encoded data with prepended parity symbols
% to encoded data with appended parity symbols prior to decoding
c21 = reshape(c1_prepend, n, []);
c22 = circshift(c21,k);
c1_append = c22(:); % BCH encoded data with appended parity symbols

% Check that the prepend-to-append conversion worked correctly.
d1_append = step(dec,c1_append);
chk = isequal(msg,d1_append)

Ниже приведен выход.

chk =

     1

Обнаружение и исправление ошибок в коде BCH с помощью MATLAB.  Следующий пример иллюстрирует результаты декодирования для поврежденного кода. Пример кодирует некоторые данные, вводит ошибки в каждое кодовое слово и пытается декодировать шумный код, используя BCH Decoder Системный объект.

n = 15; k = 5; % Codeword length and message length
[gp,t] = bchgenpoly(n,k); % t is error-correction capability.
nw = 4; % Number of words to process
msgw = randi([0 1], nw*k, 1); % Random k-symbol messages
enc = comm.BCHEncoder(n,k,gp);
dec = comm.BCHDecoder(n,k,gp);
c = step(enc, msgw); % Encode the data.
noise = randerr(nw,n,t); % t errors per codeword
noisy = noise';
noisy = noisy(:);
cnoisy = mod(c + noisy,2); % Add noise to the code.
[dc, nerrs] = step(dec, cnoisy); % Decode cnoisy.

% Check that the decoding worked correctly.
chk2 = isequal(dc,msgw)
nerrs % Find out how many errors have been corrected.

Заметьте, что массив значений шума содержит двоичные значения и что операция сложения   c + noise происходит в поле Галуа GF (2), потому что c - массив полей Галуа в GF (2).

Ниже приведены выходы из примера. Ненулевое значение ans указывает, что декодеру удалось исправить поврежденные кодовые слова и восстановить исходное сообщение. Значения в векторе nerrs указать, что декодер исправил t ошибки в каждом кодовом слове.

chk2 =

     1


nerrs =

     3
     3
     3
     3

Чрезмерный шум в кодовых словах BCH

В предыдущем примере BCH Decoder Системный объект исправил все ошибки. Однако каждый код BCH имеет конечную возможность исправления ошибок. Чтобы узнать больше о том, как BCH Decoder Системный объект ведет себя, когда шум чрезмерен, см. Аналогичное обсуждение для кодов Рида-Соломона в Избыточном Шуме в Кодовых Словах Рида-Соломона.

Алгоритмы декодирования только ошибок BCH и RS

Обзор.  Алгоритм декодирования только для ошибок, используемый для кодов BCH и RS, может быть описан следующими шагами (разделы 5.3.2, 5.4 и 5.6 в [2]).

Дальнейшее описание нескольких этапов приведено в следующих разделах.

Вычисление синдрома.  Для узкополосных кодов 2 t терминами $$S(z)$$ вычисляют путем оценки принятого кодового слова при последовательных степенях α (примитивный элемент поля) от 0 до 2 t -1. Другими словами, если предположить, что индексация кодовых слов на основе одного$$C(z)$$ и полином синдрома $$S(z)$$, и что кодовые слова имеют вид $$[c_1{c}_1\mathrm{...}{c}_N]$$, затем каждый термин $$S_i$$ из $$S(z)$$ дается как

Вычисление полинома локатора ошибок.  Полином locator error, в z, найден с помощью алгоритма Берлекампа. Полное описание этого алгоритма найдено в [2], но мы результируем алгоритм следующим образом.

Зададим следующие переменные.

Следующая диаграмма показывает, что повторяющаяся процедура (т.е. алгоритм Berlekamp) раньше находила Λ (<reservedrangesplaceholder0>).

Вычисление полинома оценки ошибок.  Полином вычислителя ошибок, $$\Omega \left(z\right)$$, просто скручивание Λ (<reservedrangesplaceholder0>) и$$S(z)$$.

Представление слов для кодов Рида-Соломона

Этот тулбокс поддерживает коды Рида-Соломона, которые используют m-битные символы вместо бит. Сообщение для [n, k] Код Рида-Соломона должен быть k-полосный массив Галуа в поле GF (2^m). Каждая запись массива должна быть целым числом от 0 до 2^m-1. Код, относящийся к этому сообщению, является n-полосный массив Галуа в GF (2^m). Длина кодового слова n должно быть от 3 до 2^m-1.

Приведенный ниже пример иллюстрирует, как представлять слова для кода [7,3] Рида-Соломона.

n = 7; k = 3; % Codeword length and message length
m = 3; % Number of bits in each symbol
msg = [1 6 4; 0 4 3]; % Message is a Galois array.
obj = comm.RSEncoder(n, k);
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
c = [c1 c2].'

Это выход

C =

     1     6     4     4     3     6     3
     0     4     3     3     7     4     7

Параметры для кодов Рида-Соломона

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

Допустимые значения целочисленных параметров.  В таблице ниже приведены значения и допустимые значения некоторых положительных целочисленных величин, связанных с кодами Рида-Соломона, как поддерживается в этом тулбоксе. Величины n и k являются входными параметрами для функций Рида-Соломона в этом тулбоксе.

Полином генератора.   rsgenpoly функция производит полиномы генератора для кодов Рида-Соломона. rsgenpoly представляет полином генератора, использующий вектор-строку Галуа, который перечисляет коэффициенты полинома в порядке убывания степеней переменной. Если каждый символ имеет m бит, вектор-строка Галуа находится в поле GF (2^m). Для примера используйте команду

r = rsgenpoly(15,13)

r = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     1     6     8

находит, что один полином генератора для кода [15,13] Рида-Соломона является X² + (А² + A) X + (A³), где A является корнем примитивного полинома по умолчанию для GF (16).

Алгебраическое выражение для полиномов генератора

Полиномы генератора, rsgenpoly имеет форму (X - A^b) ( X - A^b+1)... ( X - A^b+2t-1), где b - целое число, A - корень примитивного полинома для поля Галуа, и t (n-k)/2. Значение по умолчанию b равно 1. The выхода from rsgenpoly является результатом умножения факторов и сбора подобных степеней X. Приведенный ниже пример проверяет эту формулу на случай [15,13] кода Рида-Соломона, используя b = 1.

n = 15;
a = gf(2,log2(n+1)); % Root of primitive polynomial
f1 = [1 a]; f2 = [1 a^2]; % Factors that form generator polynomial
f = conv(f1,f2) % Generator polynomial, same as r above.

Создайте и декодируйте коды Рида-Соломона

The RS Encoder и RS Decoder Системные объекты создают и декодируют коды Рида-Соломона, используя данные, описанные в Represent Words для кодов Рида-Соломона и параметров для кодов Рида-Соломона.

Этот раздел иллюстрирует, как использовать RS Encoder и RS Decoder Системные объекты. Темы:

• Синтаксис кодирования Рида-Соломона в MATLAB

• Обнаружение и исправление ошибок в коде Рида-Соломона с помощью MATLAB

• Чрезмерный шум в кодовых словах Рида-Соломона

• Создайте укороченные коды Рида-Соломона

Синтаксис кодирования Рид-Соломона в MATLAB.  Приведенный ниже пример иллюстрирует несколько способов кодирования и декодирования данных с помощью кода [15,13] Рида-Соломона. Пример показывает, что вы можете

Этот пример также показывает, что соответствующие синтаксисы RS Encoder и RS Decoder Системные объекты используют те же входные параметры, кроме первого входного параметра.

m = 4; % Number of bits in each symbol
n = 2^m-1; k = 13; % Codeword length and message length
msg = randi([0 m-1],4*k,1); % Four random integer messages

% Simplest syntax for encoding
hEnc = comm.RSEncoder(n,k);
hDec = comm.RSDecoder(n,k);
c1 = step(hEnc, msg);
d1 = step(hDec, c1);


% Vary the generator polynomial for the code.
release(hEnc), release(hDec)
hEnc.GeneratorPolynomialSource = 'Property';
hDec.GeneratorPolynomialSource = 'Property';
hEnc.GeneratorPolynomial       = rsgenpoly(n,k,19,2);
hDec.GeneratorPolynomial       = rsgenpoly(n,k,19,2);
c2 = step(hEnc, msg);
d2 = step(hDec, c2);

% Vary the primitive polynomial for GF(16).
release(hEnc), release(hDec)
hEnc.PrimitivePolynomialSource = 'Property';
hDec.PrimitivePolynomialSource = 'Property';
hEnc.GeneratorPolynomialSource = 'Auto';
hDec.GeneratorPolynomialSource = 'Auto';
hEnc.PrimitivePolynomial       = [1 1 0 0 1];
hDec.PrimitivePolynomial	   = [1 1 0 0 1];
c3 = step(hEnc, msg);
d3 = step(hDec, c3);

% Check that the decoding worked correctly.
chk = isequal(d1,msg) & isequal(d2,msg) & isequal(d3,msg)

% The following code shows how to perform the encoding and decoding
% operations if one chooses to prepend the parity symbols.

% Steps for converting encoded data with appended parity symbols
% to encoded data with prepended parity symbols
c31 = reshape(c3, n, []);
c32 = circshift(c31,n-k);
c3_prepend = c32(:); % RS encoded data with prepended parity symbols

% Steps for converting encoded data with prepended parity symbols
% to encoded data with appended parity symbols prior to decoding
c34 = reshape(c3_prepend, n, []);
c35 = circshift(c34,k);
c3_append = c35(:); % RS encoded data with appended parity symbols

% Check that the prepend-to-append conversion worked correctly.
d3_append = step(hDec,c3_append);
chk = isequal(msg,d3_append)

Это выход

chk =

     1

Обнаружение и исправление ошибок в коде Рида-Соломона с помощью MATLAB.  Приведенный ниже пример иллюстрирует результаты декодирования для поврежденного кода. Пример кодирует некоторые данные, вводит ошибки в каждое кодовое слово и пытается декодировать шумный код, используя RS Decoder Системный объект.

m = 3; % Number of bits per symbol
n = 2^m-1; k = 3; % Codeword length and message length
t = (n-k)/2; % Error-correction capability of the code
nw = 4; % Number of words to process
msgw = randi([0 n],nw*k,1); % Random k-symbol messages
hEnc = comm.RSEncoder(n,k);
hDec = comm.RSDecoder(n,k);
c = step(hEnc, msgw); % Encode the data.
noise = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t); % t errors per codeword
noisy = noise';
noisy = noisy(:);
cnoisy = gf(c,m) + noisy; % Add noise to the code under gf(m) arithmetic.
[dc nerrs] = step(hDec, cnoisy.x); % Decode the noisy code.
% Check that the decoding worked correctly.
isequal(dc,msgw)
nerrs % Find out how many errors hDec corrected.

Массив значений шума содержит целые числа от 1 до 2^mи операцию сложения   c + noise происходит в поле Галуа GF (2^m) потому что c - массив полей Галуа в GF (2^m).

Ниже приведены выходы из примера. Ненулевое значение ans указывает, что декодеру удалось исправить поврежденные кодовые слова и восстановить исходное сообщение. Значения в векторе nerrs указывает, что декодер исправлен t ошибки в каждом кодовом слове.

ans =

     1

nerrs =

     2
     2
     2
     2

Чрезмерный шум в кодовых словах Рида-Соломона.  В предыдущем примере RS Encoder Системный объект исправил все ошибки. Однако каждый код Рида-Соломона имеет конечную возможность исправления ошибок. Если шум настолько велик, что поврежденное кодовое слово слишком далеко на расстоянии Хемминга от правильного кодового слова, это означает, что или

В обоих случаях декодер возвращает неправильное сообщение. Однако можно сказать, когда происходит отказ декодирования из-за RS Decoder Системный объект также возвращает значение -1 на его втором выходе.

Чтобы изучить случаи, когда кодовые слова являются слишком шумными для успешного декодирования, измените предыдущий пример так, чтобы определение noise является

noise = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t+1); % t+1 errors/row

Создайте укороченные коды Рида-Соломона.  Каждый энкодер Рида-Соломона использует длину кодового слова, которая равна 2^m-1 для целого числа m. Укороченный код Рида-Соломона - это код, в котором длина кодового слова не равна 2^m-1. Укороченный [n, k] Код Рида-Соломона неявно использует энкодер [_n1, _k1], где

The RS Encoder Системный объект поддерживает укороченные коды, используя те же синтаксисы, которые он использует для незащищенных кодов. Вам не нужно явным образом указывать, что вы хотите использовать укороченный код.

hEnc = comm.RSEncoder(7,5);
ordinarycode = step(hEnc,[1 1 1 1 1]');
hEnc = comm.RSEncoder(5,3);
shortenedcode = step(hEnc,[1 1 1 ]');

Как RS Encoder Системный объект создает укороченный код

При создании укороченного кода RS Encoder Системный объект выполняет следующие шаги:

Следующий пример иллюстрирует этот процесс.

n = 12; k = 8; % Lengths for the shortened code
m = ceil(log2(n+1)); % Number of bits per symbol
msg = randi([0 2^m-1],3*k,1); % Random array of 3 k-symbol words
hEnc = comm.RSEncoder(n,k);
code = step(hEnc, msg); % Create a shortened code.

% Do the shortening manually, just to show how it works.
n_pad = 2^m-1; % Codeword length in the actual encoder
k_pad = k+(n_pad-n); % Messageword length in the actual encoder
hEnc = comm.RSEncoder(n_pad,k_pad);
mw = reshape(msg,k,[]); % Each column vector represents a messageword
msg_pad = [zeros(n_pad-n,3); mw]; % Prepend zeros to each word.
msg_pad = msg_pad(:);
code_pad = step(hEnc,msg_pad); % Encode padded words.
cw = reshape(code_pad,2^m-1,[]); % Each column vector represents a codeword
code_eqv = cw(n_pad-n+1:n_pad,:); % Remove extra zeros.
code_eqv = code_eqv(:);
ck = isequal(code_eqv,code); % Returns true (1).

Найдите полином генератора

Чтобы найти полином генератора для циклического, BCH или кода Рида-Соломона, используйте cyclpoly, bchgenpoly, или rsgenpoly функция, соответственно. Команды

genpolyCyclic = cyclpoly(15,5) % 1+X^5+X^10
genpolyBCH = bchgenpoly(15,5)  % x^10+x^8+x^5+x^4+x^2+x+1
genpolyRS = rsgenpoly(15,5)

найти полиномы генератора для блочных кодов разных типов. Ниже приведен выход.

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1

 
genpolyBCH = GF(2) array. 
 
Array elements = 
 
     1     0     1     0     0     1     1     0     1     1     1

 
genpolyRS = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
     1     4     8    10    12     9     4     2    12     2     7

Форматы этих выходов варьируются:

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

Алгебраическое выражение для полиномов генератора.  Полиномы генератора, произведенные bchgenpoly и rsgenpoly иметь форму (X - A^b) ( X - A^b+1)... ( X - A^b+2t-1), где A является примитивным элементом для соответствующего поля Галуа, и b и t являются целыми числами. Для получения дополнительной информации об этом выражении см. страницы с описанием функций.

Примеры Рида Соломона с укорочением, проколом и стиранием

В этом разделе демонстрационный пример кодирования Рида Соломона с укорочением, проколом и стираниями построен с увеличением сложности коррекции ошибок.

Пример энкодера с укорочением и проколом.  Следующие рисунки показывают демонстрационный пример (7,3) Рида Соломона с энкодером укорочения и прокола.

На этом рисунке источник сообщения выводит два информационных символа, обозначенных _I1I2. (Для примера BCH символы являются просто двоичными битами.) Поскольку код является укороченным (7,3) кодом, нуль должен быть добавлен перед информационными символами, получая трехсимвольное сообщение _0I1I2. Модифицированная последовательность сообщений затем кодируется RS, и добавленная информация нули впоследствии удаляется, что приводит к результату _I1I2P1P2P3P4. (В этом примере биты четности находятся в конце кодового слова.)

Операция прокола управляется вектором прокола, который в этом случае равен 1011. В векторе прокола значение 1 означает, что символ сохранен, а значение 0 означает, что символ выбрасывается. В этом примере операция прокалывания удаляет второй символ четности, получая конечный вектор _I1I2P1P3P4.

Пример декодера с укорочением и проколом.  Следующий рисунок показов, как энкодер RS работает с укороченным и проколотым кодовым словом.

Этот случай соответствует операциям энкодера, показанным на рисунке RS-энкодера с укорочением и проколом. Как показано на предыдущем рисунке, энкодер принимает (5,2) кодовое слово, поскольку оно было укорочено от (7,3) кодового слова одним символом, и один символ также был проколот.

В качестве первого шага декодер добавляет стирание, обозначенное E, во второе положение четности кодового слова. Это соответствует вектору 1011 прокола. Добавление нуля учитывает сокращение, таким же образом как показано на предыдущем рисунке. Одно стирание не превышает возможности исправления стирания кода, что может исправить четыре стирания. Операция декодирования результатов в трехсимвольном сообщении _DI1I2. Первый символ усечен, как и на предыдущем рисунке, получая конечный выход _I1I2.

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

На этом рисунке демодулятор получает вектор _I1I2P1P3P4, который подает энкодер Демодулятор заявляет, что два из пяти принятых символов являются достаточно ненадежными, чтобы быть стерты, так что символы 2 и 5 считаются стираниями. Вектор 01001, обеспечиваемый внешним источником, указывает на эти стирания. В векторе стирания значение 1 означает, что символ должен быть заменен символом стирания, а значение 0 означает, что символ передается без изменений.

Декодер блокирует прием кодового слова и вектора стирания и выполняет стирание, обозначенное вектором 01001. В векторе стирания значение 1 означает, что символ должен быть заменен символом стирания, а значение 0 означает, что символ передается без изменений. Получившийся вектор кодового слова _I1EP1P3E, где E является символом стирания.

Кодовое слово затем деформируется в соответствии с вектором прокола, используемым в операции кодирования (т.е. 1011). Таким образом, символ стирания вставляется между _P1 и _P3, получая вектор _I1EP1EP3E кодового слова.

Непосредственно перед декодированием сложение нулей в начале информационного вектора учитывает сокращение. Получившийся вектор _0I1EP1EP3E, так что (7,3) кодовое слово посылается в алгоритм Берлекампа.

Это кодовое слово декодируется, получая трехсимвольное сообщение _DI1I2 (где D относится к фиктивному символу). Наконец, удаление символа D из вектора сообщения учитывает сокращение и приводит к выражениям исходного вектора _I1I2.

Для получения дополнительной информации смотрите Кодирование Рида-Соломона с стираниями, проколы и укорочение в примере Simulink.

Терминология поля Галуа

Обсуждение полей Галуа в этом документе использует несколько терминов, которые не используются последовательно в литературе. Принятые здесь определения содержатся в van Lint [4]:

Определения подразумевают, что примитивный элемент является корнем соответствующего примитивного полинома.

Представление элементов полей Галуа

• Обзор разделов

• Создание массива полей Галуа

• Пример: Создание переменных поля Галуа

• Пример: Представление элементов GF (8)

• Как целые числа соответствуют элементам поля Галуа

• Пример: Представление примитивного элемента

• Примитивные полиномы и представления элемента

Обзор разделов.  В этом разделе описывается, как создать массив полей Галуа, который является выражением MATLAB, которое представляет элементы массива поля Галуа. В этом разделе также описывается, как техническое вычислительное программное обеспечение MATLAB интерпретирует числа, которые вы используете в представлении, и включает несколько примеров.

Создание массива полей Галуа.  Чтобы начать работу с данными из поля Галуа GF (2^m), необходимо задать контекст путем связи данных с важной информацией о поле. gf функция выполняет эту ассоциацию и создает массив полей Галуа в MATLAB. Эта функция принимает как входы

Выходные выходы gf функция является переменной, которую MATLAB распознает как массив полей Галуа, а не как массив целых чисел. В результате, когда вы манипулируете переменной, MATLAB работает в указанном поле Galois. Для примера, если вы применяете log функция для массива полей Галуа, MATLAB вычисляет логарифм в поле Галуа, а не в поле вещественных или комплексных чисел.

Когда MATLAB неявно создает массив полей Галуа

Некоторые операции с массивами полей Галуа требуют нескольких аргументов. Если вы задаете один аргумент, который является массивом полей Галуа, и другой, который является обычным массивом MATLAB, MATLAB интерпретирует оба как массивы полей Галуа в том же поле. Это неявно вызывает gf функция на обычном массиве MATLAB. Этот неявный вызов упрощает синтаксис, потому что можно опустить некоторые ссылки на gf функция. Пример упрощения см. в Примере: Сложение и вычитание.

Пример: Создание переменных поля Галуа.  Приведенный ниже код создает вектор-строку, значения которого указаны в поле GF (4), а затем добавляет строку к себе.

x = 0:3; % A row vector containing integers
m = 2; % Work in the field GF(2^2), or, GF(4).
a = gf(x,m) % Create a Galois array in GF(2^m).

b = a + a % Add a to itself, creating b.

Это выход

a = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)

Array elements =

     0     1     2     3


b = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)

Array elements =

     0     0     0     0

На выход показаны значения массивов полей Галуа с именем a и b. Каждый выходной раздел указывает

Команда, которая создает b показывает, как, определив переменную a в качестве массива полей Галуа можно добавить a сам по себе при помощи обыкновенных + оператор. MATLAB выполняет операцию векторизации сложения в поле GF (4). Этот выход показывает, что

Пример: Представление элементов GF (8 ). Чтобы проиллюстрировать, что означают элементы массива в массиве Галуа, в таблице ниже перечислены элементы поля GF (8) как целые числа и как полиномы в примитивном элементе, А. Таблица должна помочь вам интерпретировать массив поля Галуа, как

gf8 = gf([0:7],3); % Galois vector in GF(2^3)

Как целые числа соответствуют элементам поля Галуа.  Основываясь на примере GF (8) выше, этот раздел объясняет интерпретацию элементов массива в массиве полей Галуа в большей общности. Поле GF (2^m) имеет 2^m отдельные элементы, которые этот тулбокс помечает как 0, 1, 2,..., 2^m-1. Эти целочисленные метки соответствуют элементам поля Галуа через полиномиальное выражение с участием примитивного элемента поля. Более конкретно, каждое целое число от 0 до 2^m-1 имеет двоичное представление в m биты. Использование бит в двоичном представлении как коэффициентов в полиноме, где наименее значимым битом является постоянный член, приводит к двоичному полиному, порядок которого не более m-1. Оценка двоичного полинома в примитивном элементе GF (2^m) ведет к элементу поля.

И наоборот, любой элемент GF (2^m) может быть выражен как двоичный полином порядка самое большее m-1, оцениваемый в примитивном элементе поля. The m-кортеж коэффициентов полинома соответствует двоичному представлению целого числа от 0 до 2^m.

Ниже приведен символический рисунок соответствия целочисленного X, представимого в двоичной форме, элементу поля Галуа. Каждый b k равен либо нулю, либо единице, в то время как A является примитивным элементом.

Пример: Представление примитивного элемента.  Приведенный ниже код задает переменную alph который представляет примитивный элемент поля GF (2⁴).

m = 4; % Or choose any positive integer value of m.
alph = gf(2,m) % Primitive element in GF(2^m)

Это выход

alph = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     2

Поле Галуа массива alph представляет примитивный элемент из-за соответствия между

Примитивные полиномы и представления элемента.  Этот раздел основан на обсуждении в Создании массива полей Галуа путем описания того, как задать свой собственный примитивный полином при создании массива полей Галуа. Темы:

Если вы выполняете много расчеты с помощью примитивного полинома без параметров, см. «Скорость» и «Примитивные полиномы Недефо».

Определение примитивного полинома

Обсуждение в «Как целые числа соответствуют элементам поля Галуа» относится к примитивному элементу, который является корнем примитивного полинома поля. Когда вы используете gf функция для создания массива полей Галуа, функция интерпретирует целые числа в массиве относительно определенного примитивного полинома по умолчанию для этого поля, если вы явным образом не задаете другой примитивный полином. Список примитивных полиномов по умолчанию находится на странице с описанием для gf функция.

Чтобы задать свой собственный примитивный полином при создании массива полей Галуа, используйте синтаксис, подобный

c = gf(5,4,25) % 25 indicates the primitive polynomial for GF(16).

вместо

c1= gf(5,4); % Use default primitive polynomial for GF(16).

Дополнительный входной параметр, 25 в этом случае задает примитивный полином для поля GF (2^m) способом, подобным представлению, описанному в «Как целые числа соответствуют элементам поля Галуа». В этом случае целое число 25 соответствует двоичному представлению 11001, которое в свою очередь соответствует полиному D⁴ + D³  + 1.

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

d = gf([1 2 3],4,25)

d = GF(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal)

Array elements =

     1     2     3

Нахождение примитивных полиномов

Вы можете использовать primpoly функция для поиска примитивных полиномов для GF (2^m) и isprimitive функция для определения, является ли полином примитивным для GF (2^m). Приведенный ниже код иллюстрирует.

m = 4;
defaultprimpoly = primpoly(m) % Default primitive poly for GF(16)
allprimpolys = primpoly(m,'all') % All primitive polys for GF(16)
i1 = isprimitive(25) % Can 25 be the prim_poly input in gf(...)?
i2 = isprimitive(21) % Can 21 be the prim_poly input in gf(...)?

Ниже приведен выход.

Primitive polynomial(s) =

D^4+D^1+1

defaultprimpoly =

    19

Primitive polynomial(s) =

D^4+D^1+1
D^4+D^3+1

allprimpolys =

    19
    25

i1 =

     1

i2 =

     0

Эффект примитивных полиномов Nondefault на числовые результаты

Большинство полей предлагают несколько вариантов для примитивного полинома, который помогает задать представление представителей поля. Когда вы используете gf функция, изменение примитивного полинома изменяет интерпретацию элементов массива и, в свою очередь, изменяет результаты некоторых последующих операций над массивом полей Галуа. Для примера, экспоненция примитивного элемента облегчает просмотр того, как примитивный полином влияет на представления элементов поля.

a11 = gf(2,3); % Use default primitive polynomial of 11.
a13 = gf(2,3,13); % Use D^3+D^2+1 as the primitive polynomial.
z = a13.^3 + a13.^2 + 1 % 0 because a13 satisfies the equation
nz = a11.^3 + a11.^2 + 1 % Nonzero. a11 does not satisfy equation.

Приведенная ниже выход показывает, что, когда примитивный полином имеет целочисленное представление 13массив поля Галуа удовлетворяет определенному уравнению. Напротив, когда примитивный полином имеет целочисленное представление 11массив поля Галуа не удовлетворяет уравнению.

z = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)

Array elements =

     0


nz = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     6

Выход, когда вы пробуете этот пример, может также включать предупреждение о интерполяционных таблицах. Это нормально, если вы не использовали gftable функция для оптимизации расчетов с использованием примитива nondefault, равного 13.

Арифметика в полях Галуа

• Обзор разделов

• Пример: Сложение и вычитание

• Пример: Умножение

• Пример: Деление

• Пример: Экспоненция

• Пример: Элементный логарифм

Обзор разделов.  Можно выполнить арифметические операции с массивами полей Galois с помощью знакомых операторов MATLAB, перечисленных в таблице ниже. Каждый раз, когда вы работаете с парой массивов полей Галуа, оба массива должны быть в одном поле Галуа.

Для умножения и деления полиномов на поле Галуа, смотрите Сложение и Вычитание Полиномов.

Пример: Сложение и вычитание.  Приведенный ниже код добавляет два массива полей Галуа, чтобы создать таблицу сложений для GF (8). В сложении используются обычные + оператор. Приведенный ниже код также показывает, как индексировать в массив addtb найти результат добавления 1 к элементам GF (8).

m = 3;
e = repmat([0:2^m-1],2^m,1);
f = gf(e,m); % Create a Galois array.
addtb = f + f' % Add f to its own matrix transpose.

addone = addtb(2,:); % Assign 2nd row to the Galois vector addone.

Ниже приведен выход.

addtb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0     1     2     3     4     5     6     7
     1     0     3     2     5     4     7     6
     2     3     0     1     6     7     4     5
     3     2     1     0     7     6     5     4
     4     5     6     7     0     1     2     3
     5     4     7     6     1     0     3     2
     6     7     4     5     2     3     0     1
     7     6     5     4     3     2     1     0

Как пример чтения этой таблицы сложения, запись (7,4) в addtb массив показывает, что gf(6,3) плюс gf(3,3) равен gf(5,3). Эквивалентно, элемент A²+ A плюс элемент A + 1 равен элементу A²+1. Эквивалентность возникает из двоичного представления 6 как 110, 3 как 011 и 5 как 101.

Вычитающая таблица, которую можно получить, заменив + по -, то же, что и addtb. Это связано с тем, что вычитание и сложение являются идентичными операциями в поле характеристики два. Фактически, нули по основной диагонали addtb иллюстрирует этот факт для GF (8).

Упрощение синтаксиса

Приведенный ниже код иллюстрирует скалярное расширение и неявное создание массива полей Галуа из обычного массива MATLAB. Массивы полей Галуа h и h1 идентичны, но создание h использует более простой синтаксис.

g = gf(ones(2,3),4); % Create a Galois array explicitly.
h = g + 5; % Add gf(5,4) to each element of g.
h1 = g + gf(5*ones(2,3),4) % Same as h.

Ниже приведен выход.

h1 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     4     4     4
     4     4     4

Заметьте, что 1 + 5 сообщается как 4 в поле Galois. Это верно, потому что 5 представляет полиномиальное выражение A²+ 1, и 1 + (A²+ 1) в GF (16) обозначает A². Кроме того, целое число, которое представляет полиномиальное выражение A² равен 4.

Пример: Умножение.  Приведенный ниже пример умножает отдельные элементы массива полей Галуа, используя .* оператор. Затем он выполняет матричное умножение, используя * оператор. Элементарное умножение создает массив, размер которого совпадает с размером входов. Напротив, умножение матрицы создает скаляр Галуа, потому что это матричный продукт вектора-строки с вектором-столбцом.

m = 5;
row1 = gf([1:2:9],m); row2 = gf([2:2:10],m);
col = row2'; % Transpose to create a column array.
ep = row1 .* row2; % Elementwise product.
mp = row1 * col; % Matrix product.

Таблица умножения для GF (8)

В качестве другого примера, код ниже умножает два вектора Галуа, используя матричное умножение. Результатом является таблица умножения для GF (8).

m = 3;
els = gf([0:2^m-1]',m);
multb = els * els' % Multiply els by its own matrix transpose.

Ниже приведен выход.

multb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0     0     0     0     0     0     0     0
     0     1     2     3     4     5     6     7
     0     2     4     6     3     1     7     5
     0     3     6     5     7     4     1     2
     0     4     3     7     6     2     5     1
     0     5     1     4     2     7     3     6
     0     6     7     1     5     3     2     4
     0     7     5     2     1     6     4     3

Пример: Деление.  Приведенные ниже примеры иллюстрируют четыре оператора деления в поле Галуа путем вычисления мультипликативных инвертов отдельных элементов и массива. Можно также вычислить инверты с помощью inv или с использованием экспоненции на -1.

Элементное деление

Этот пример делит 1 на каждый из отдельных элементов в массиве полей Галуа, используя ./ и .\ операторы. Эти два оператора различаются только своей последовательностью входных параметров. Каждый частный вектор приводит мультипликативные обратные значения ненулевых элементов поля. В этом примере MATLAB расширяет скаляр 1 до размера nz перед вычислением; также можно использовать в качестве аргументов два массива одинакового размера.

m = 5;
nz = gf([1:2^m-1],m); % Nonzero elements of the field
inv1 = 1 ./ nz; % Divide 1 by each element.
inv2 = nz .\ 1; % Obtain same result using .\ operator.

Матричное деление

Этот пример делит массив тождеств на квадратный массив поля Галуа mat использование / и \ операторы. Каждая частная матрица является мультипликативной обратной mat. Заметьте, как оператор транспонирования (') появляется в эквивалентной операции с помощью \. Для квадратных матриц последовательность операций транспонирования ненужна, но для нескверных матриц она необходима.

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minv1 = eye(3) / mat; % Compute matrix inverse.
minv2 = (mat' \ eye(3)')'; % Obtain same result using \ operator.

Пример: Экспоненция.  Приведенные ниже примеры иллюстрируют, как вычислить целочисленные степени массива полей Галуа. Чтобы выполнить матричную экспоненцию для массива полей Галуа, необходимо использовать квадратный массив полей Галуа в качестве основы и обыкновенный (не Галуа) целочисленный скаляр в качестве экспоненты.

Элементная экспоненция

Этот пример вычисляет степени примитивного элемента, A, поля Галуа. Затем он использует эти отдельно вычисленные степени, чтобы вычислить примитивный полином по умолчанию в A. Ответ в нуле показывает, что A является корнем примитивного полинома. The .^ оператор экспонентирует каждый элемент массива независимо.

m = 3;
av = gf(2*ones(1,m+1),m); % Row containing primitive element
expa = av .^ [0:m]; % Raise element to different powers.
evp = expa(4)+expa(2)+expa(1) % Evaluate D^3 + D + 1.

Ниже приведен выход.

evp = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0

Матричная экспоненция

Этот пример вычисляет обратную матрицу квадратной матрицы, повышая матрицу до степени -1. Это также поднимает квадратную матрицу в степени 2 и -2.

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minvs = mat ^ (-1); % Matrix inverse
matsq = mat^2; % Same as mat * mat
matinvssq = mat^(-2); % Same as minvs * minvs

Пример: Элементный логарифм.  Приведенный ниже код вычисляет логарифм элементов массива полей Галуа. Выход указывает, как выразить каждый ненулевой элемент GF (8) как степень примитивного элемента. Логарифм нулевого элемента поля не определен.

gf8_nonzero = gf([1:7],3); % Vector of nonzero elements of GF(8)
expformat = log(gf8_nonzero) % Logarithm of each element

Это выход

expformat =

     0     1     3     2     6     4     5

Как пример того, как интерпретировать выход, рассмотрим последнюю запись в каждом векторе в этом примере. Можно сделать вывод, что элемент gf(7,3) в GF (8) могут быть выражены как

Логические операции в полях Галуа

• Обзор разделов

• Проверка на равенство

• Проверка на ненулевые значения

Обзор разделов.  Можно применить логические тесты к массивам полей Galois и получить логический массив. Некоторыми важными типами тестов являются проверка на равенство двух массивов полей Галуа и проверка на ненулевые значения в массиве полей Галуа.

Проверка на равенство.  Чтобы сравнить соответствующие элементы двух массивов полей Галуа с одинаковым размером, используйте операторы == и ~=. Результатом является логический массив, каждый элемент которого указывает на правду или ложность соответствующего элементарного сравнения. Если вы используете те же операторы, чтобы сравнить скаляр с массивом полей Галуа, техническое вычислительное программное обеспечение MATLAB сравнивает скаляр с каждым элементом массива, получая логический массив одинакового размера.

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg1 = (r1 .* r2 == [1 1 1]) % Does each element equal one?
lg2 = (r1 .* r2 == 1) % Same as above, using scalar expansion
lg3 = (r1 ~= r2) % Does each element differ from its inverse?

Ниже приведен выход.

lg1 =

     1     1     1


lg2 =

     1     1     1


lg3 =

     0     1     1

Сравнение isequal и = =

Чтобы сравнить целые массивы и получить логический скалярный результат, а не логический массив, используйте встроенный isequal функция. Однако isequal использует строгие правила для его сравнения и возвращает значение 0 (false), если вы сравниваете

Приведенный ниже пример иллюстрирует это различие между == и isequal.

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg4 = isequal(r1 .* r2, [1 1 1]); % False
lg5 = isequal(r1 .* r2, gf(1,m)); % False
lg6 = isequal(r1 .* r2, gf([1 1 1],m)); % True

Проверка на ненулевые значения.  Чтобы проверить ненулевые значения в векторе Галуа или в столбцах массива полей Галуа, который имеет более одной строки, используйте any или all функция. Эти две функции ведут себя так же, как и обычные функции MATLAB any и all, за исключением того, что они рассматривают только базовые элементы массива, игнорируя при этом информацию о том, в каком поле Галуа находятся элементы. Примеры приведены ниже.

m = 3; randels = gf(randi([0 2^m-1],6,1),m);
if all(randels) % If all elements are invertible
    invels = randels .\ 1; % Compute inverses of elements.
else
    disp('At least one element was not invertible.');
end
alph = gf(2,4);
poly = 1 + alph + alph^3;
if any(poly) % If poly contains a nonzero value
    disp('alph is not a root of 1 + D + D^3.');
end
code = [0:4 4 0; 3:7 4 5]
if all(code,2) % Is each row entirely nonzero?
    disp('Both codewords are entirely nonzero.');
else
    disp('At least one codeword contains a zero.');
end

Матричные манипуляции в полях Галуа

• Основные манипуляции с полевыми массивами Галуа

• Основные сведения о полевых массивах Галуа

Основные манипуляции с полевыми массивами Галуа.  Основные операции над массивами Галуа приведены в таблице ниже. Функциональность этих операций аналогична операциям MATLAB, имеющим тот же синтаксис.

В приведенном ниже коде используются некоторые из этих синтаксисов.

m = 4; a = gf([0:15],m);
a(1:2) = [13 13]; % Replace some elements of the vector a.
b = reshape(a,2,8); % Create 2-by-8 matrix.
c = [b([1 1 2],1:3); a(4:6)]; % Create 4-by-3 matrix.
d = [c, a(1:4)']; % Create 4-by-4 matrix.
dvec = diag(d); % Extract main diagonal of d.
dmat = diag(a(5:9)); % Create 5-by-5 diagonal matrix
dtril = tril(d); % Extract upper and lower triangular
dtriu = triu(d); % parts of d.

Основные сведения о полевых массивах Галуа.  Можно определить длину вектора Галуа или размер любого массива полей Галуа, используя length и size функций. Функциональность для массивов полей Галуа аналогична функциональности операций MATLAB для обычных массивов, за исключением того, что выходные аргументы из size и length всегда являются целыми числами, а не массивами полей Галуа. Приведенный ниже код иллюстрирует использование этих функций.

m = 4; e = gf([0:5],m); f = reshape(e,2,3);
lne = length(e); % Vector length of e
szf = size(f); % Size of f, returned as a two-element row
[nr,nc] = size(f); % Size of f, returned as two scalars
nc2 = size(f,2); % Another way to compute number of columns

Положения ненулевых элементов

Другой тип информации, которую вы, возможно, захотите определить из массива полей Галуа, - это положения ненулевых элементов. Для обычного массива MATLAB можно использовать find функция. Однако для массива полей Галуа следует использовать find в сочетании с ~= оператор, как проиллюстрировано.

x = [0 1 2 1 0 2]; m = 2; g = gf(x,m);
nzx = find(x); % Find nonzero values in the ordinary array x.
nzg = find(g~=0); % Find nonzero values in the Galois array g.

Линейная алгебра в полях Галуа

• Инвертирование матриц и вычисление определяющих

• Вычислительные ранги

• Факторизация квадратных матриц

• Решение линейных уравнений

Инвертирование матриц и вычислительные определяющие.  Чтобы инвертировать квадратный массив поля Галуа, используйте inv функция. Связано с тем, det функция, которая вычисляет определяющего массива полей Галуа. Оба inv и det вести себя как их обычные аналоги MATLAB, за исключением того, что они выполняют расчеты в поле Галуа вместо в поле комплексных чисел.

Код ниже иллюстрирует инверсию матрицы и определяющие расчеты.

m = 4;
randommatrix = gf(randi([0 2^m-1],4,4),m);
gfid = gf(eye(4),m);
if det(randommatrix) ~= 0
    invmatrix = inv(randommatrix);
    check1 = invmatrix * randommatrix;
    check2 = randommatrix * invmatrix;
    if (isequal(check1,gfid) & isequal(check2,gfid))
        disp('inv found the correct matrix inverse.');
    end
else
    disp('The matrix is not invertible.');
end

Выходы этого примера являются любым из этих двух сообщений, в зависимости от того, является ли случайным образом сгенерированная матрица несингулярной или сингулярной.

inv found the correct matrix inverse.
The matrix is not invertible.

Вычислительные ранги.  Чтобы вычислить ранг массива полей Галуа, используйте rank функция. Он ведет себя как обычный MATLAB rank функция, если задан только один входной параметр. Приведенный ниже пример иллюстрирует, как найти ранг квадратного и нескверного полевых массивов Галуа.

m = 3;
asquare = gf([4 7 6; 4 6 5; 0 6 1],m);
r1 = rank(asquare);
anonsquare = gf([4 7 6 3; 4 6 5 1; 0 6 1 1],m);
r2 = rank(anonsquare);
[r1 r2]

Это выход

ans =

     2     3

Значения r1 и r2 указать, что asquare имеет меньше, чем полный ранг, но это anonsquare имеет полный ранг.

Факторизация квадратных матриц.  Чтобы выразить квадратный массив поля Галуа (или его сочетание) как продукт нижнего треугольного массива поля Галуа и верхнего треугольного массива поля Галуа, используйте lu функция. Эта функция принимает один входной параметр и выдает ровно два или три выходных аргументов. Он ведет себя как обычный MATLAB lu функция при задании того же синтаксиса. Приведенный ниже пример иллюстрирует, как определить использование lu.

tofactor = gf([6 5 7 6; 5 6 2 5; 0 1 7 7; 1 0 5 1],3);
[L,U]=lu(tofactor); % lu with two output arguments
c1 = isequal(L*U, tofactor) % True
tofactor2 = gf([1 2 3 4;1 2 3 0;2 5 2 1; 0 5 0 0],3);
[L2,U2,P] = lu(tofactor2); % lu with three output arguments
c2 = isequal(L2*U2, P*tofactor2) % True

Решение линейных уравнений.  Чтобы найти конкретное решение линейного уравнения в поле Галуа, используйте \ или / оператор на массивах полей Галуа. Таблица ниже указывает уравнение, которое адресует каждый оператор, принимая, что A и B являются ранее заданными массивами полей Галуа.

Результаты синтаксиса в таблице зависят от характеристик массива полей Галуа A:

Пример: Решение линейных уравнений

Приведенные ниже примеры иллюстрируют, как найти конкретные решения линейных уравнений над полем Галуа.

m = 4;
A = gf(magic(3),m); % Square nonsingular matrix
Awide=[A, 2*A(:,3)]; % 3-by-4 matrix with redundancy on the right
Atall = Awide'; % 4-by-3 matrix with redundancy at the bottom
B = gf([0:2]',m);
C = [B; 2*B(3)];
D = [B; B(3)+1];
thesolution = A \ B; % Solution of A * x = B
thesolution2 = B' / A; % Solution of x * A = B'
ck1 = all(A * thesolution == B) % Check validity of solutions.
ck2 = all(thesolution2 * A == B')
% Awide * x = B has infinitely many solutions. Find one.
onesolution = Awide \ B;
ck3 = all(Awide * onesolution == B) % Check validity of solution.
% Atall * x = C has a solution.
asolution = Atall \ C;
ck4 = all(Atall * asolution == C) % Check validity of solution.
% Atall * x = D has no solution.
notasolution = Atall \ D;
ck5 = all(Atall * notasolution == D) % It is not a valid solution.

Выход из этого примера указывает, что все проверки валидности верны (1), кроме ck5, что ложно (0).

Операции обработки сигналов в полях Галуа

• Обзор разделов

• Фильтрация

• Скручивание

• Дискретное преобразование Фурье

Обзор разделов.  Можно выполнить некоторые операции обработки сигналов на массивах полей Галуа, таких как фильтрация, свертка и дискретное преобразование Фурье.

В этом разделе описывается, как выполнить эти операции.

Другая информация о соответствующих операциях для обычных векторов действительных чисел находится в документации Signal Processing Toolbox™.

Фильтрация.  Чтобы фильтровать вектор Галуа, используйте filter функция. Он ведет себя как обычный MATLAB filter функция, если заданы только три входных параметров.

m = 1; % Work in GF(2).
b = gf([1 0 0 1 0 1 0 1],m); % Numerator
a = gf([1 0 1 1],m); % Denominator
x = gf([1,zeros(1,19)],m);
y = filter(b,a,x); % Filter x.
figure; stem(y.x); % Create stem plot.
axis([0 20 -.1 1.1])

Свертки.  Программное обеспечение Communications Toolbox предлагает два эквивалентных способа свертки пары векторов Галуа:

Пример

Вычисляет матрицу свертки для вектора b в ГФ (4). Представьте коэффициенты числителя для цифрового фильтра, а затем проиллюстрировайте два эквивалентных способа свертки b с x над полем Галуа.

m = 2; b = gf([1 2 3]',m);
n = 3; x = gf(randi([0 2^m-1],n,1),m);
C = convmtx(b,n); % Compute convolution matrix.
v1 = conv(b,x); % Use conv to convolve b with x
v2 = C*x; % Use C to convolve b with x.

Дискретное преобразование Фурье.  Дискретное преобразование Фурье является важным инструментом в цифровой обработке сигналов. Этот тулбокс предлагает эти инструменты, которые помогут вам обработать дискретные преобразования Фурье:

Во всех случаях преобразовываемый вектор должен быть вектором Галуа длины 2^m-1 в поле GF (2^m). Следующий пример иллюстрирует использование этих функций. Можно проверить, используя isequal функции, что y равен y1, z равен z1, и z равен x.

m = 4;
x = gf(randi([0 2^m-1],2^m-1,1),m); % A vector to transform
alph = gf(2,m);
dm = dftmtx(alph);
idm = dftmtx(1/alph);
y = dm*x; % Transform x using the result of dftmtx.
y1 = fft(x); % Transform x using fft.
z = idm*y; % Recover x using the result of dftmtx(1/alph).
z1 = ifft(y1); % Recover x using ifft.

Полиномы над полями Галуа

• Обзор разделов

• Сложение и вычитание полиномов

• Умножение и деление полиномов

• Оценка полиномов

• Корни полиномов

• Корни двоичных полиномов

• Минимальные полиномы

Обзор разделов.  Можно использовать векторы Галуа, чтобы представлять полиномы в неопределенной величине x с коэффициентами в поле Галуа. Сформируйте представление путем перечисления коэффициентов полинома в векторе в порядке убывания степеней x. Например, вектор

gf([2 1 0 3],4)

представляет полином Ax³ + 1x² + 0x + (A + 1), где

Затем можно использовать такой вектор Галуа, чтобы выполнить арифметику с, вычислить и найти корни полиномов. Можно также найти минимальные полиномы элементов массива поля Галуа.

Сложение и вычитание полиномов.  Чтобы добавить и вычесть полиномы, используйте + и - на векторах Галуа равной длины, которые представляют полиномы. Если один полином имеет более низкую степень, чем другой, необходимо дополнить более короткий вектор нулями в начале, чтобы два вектора имели одинаковую длину. Приведенный ниже пример показов, как добавить полином степени 1 и степени 2.

lin = gf([4 2],3); % A^2 x + A, which is linear in x
linpadded = gf([0 4 2],3); % The same polynomial, zero-padded
quadr = gf([1 4 2],3); % x^2 + A^2 x + A, which is quadratic in x
% Can't do lin + quadr because they have different vector lengths.
sumpoly = [0, lin] + quadr; % Sum of the two polynomials
sumpoly2 = linpadded + quadr; % The same sum

Умножение и деление полиномов.  Чтобы умножить и разделить полиномы, используйте conv и deconv на векторах Галуа, которые представляют полиномы. Умножение и деление полиномов эквивалентно свертке и деконволюции векторов. deconv функция возвращает частный для двух полиномов, а также оставшийся полином. Примеры приведены ниже.

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
bpoly = gf([1 1],m); % x + 1
xpoly = gf([1 0],m); % x
% Product is A^2 x^3 + x^2 + (A^2 + A) x + (A + 1).
cpoly = conv(apoly,bpoly);
[a2,remd] = deconv(cpoly,bpoly); % a2==apoly. remd is zero.
[otherpol,remd2] = deconv(cpoly,xpoly); % remd is nonzero.

Операторы умножения и деления в Арифметике в Полях Галуа умножают элементы или матрицы, а не полиномы.

Оценка полиномов.  Чтобы вычислить полином в элемент массива поле Галуа, используйте polyval. Он ведет себя как обычный MATLAB polyval функция, если заданы только два входных параметров. Приведенный ниже пример оценивает полином из нескольких элементов поля и проверяет результаты с помощью .^ и .* в поле.

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
x0 = gf([0 1 2],m); % Points at which to evaluate the polynomial
y = polyval(apoly,x0)

a = gf(2,m); % Primitive element of the field, corresponding to A.
y2 = a.^2.*x0.^2 + (a.^2+1).*x0 + (a+1) % Check the result.

Ниже приведен выход.

y = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     3     2    10


y2 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     3     2    10

Первый элемент y оценивает полином в 0 и, следовательно, возвращает постоянный член полинома 3.

Корни полиномов.  Чтобы найти корни полинома в поле Галуа, используйте roots функция на векторе Галуа, который представляет полином. Эта функция находит корни, которые находятся в том же поле, в котором находится вектор Галуа. Количество раз, когда запись появляется в векторе выхода от roots является в точности его кратностью как корня полинома.

Приведенные ниже примеры находят корни кубических полиномов в GF (8).

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

Корни двоичных полиномов.  В частном случае полинома, имеющего двоичные коэффициенты, также легко найти корни, которые существуют в поле расширения. Это связано с тем, что элементы 0 и 1 иметь одинаковое однозначное представление во всех полях характеристики два. Чтобы найти корни двоичного полинома в поле расширения, примените roots функция вектору Галуа в поле расширения, элементы массива которого являются двоичными коэффициентами полинома.

Приведенный ниже пример ищет корни двоичного полинома в различных полях.

gf2poly = gf([1 1 1],1); % x^2 + x + 1 in GF(2)
noroots = roots(gf2poly); % No roots in the ground field, GF(2)
gf4poly = gf([1 1 1],2); % x^2 + x + 1 in GF(4)
roots4 = roots(gf4poly); % The roots are A and A+1, in GF(4).
gf16poly = gf([1 1 1],4); % x^2 + x + 1 in GF(16)
roots16 = roots(gf16poly); % Roots in GF(16)
checkanswer4 = polyval(gf4poly,roots4); % Zero vector
checkanswer16 = polyval(gf16poly,roots16); % Zero vector

Корни полинома не существуют в GF (2), поэтому noroots - пустой массив. Однако корни полинома существуют в GF (4), а также в GF (16), так что roots4 и roots16 являются непустыми.

Заметьте, что roots4 и roots16 не равны друг другу. Они различаются следующими способами:

Минимальные полиномы.  Минимальный полином элемента GF (2^m) - полином с двоичным коэффициентом наименьшей степени, имеющий этот элемент в качестве корня в GF (2^m). Чтобы найти минимальный полином элемента или вектора-столбца элементов, используйте minpol функция.

Приведенный ниже код находит, что минимальный полином gf(6,4) является D² + D + 1 и затем проверяет, что gf(6,4) действительно является одним из корней этого полинома в поле GF (16).

m = 4;
e = gf(6,4);
em = minpol(e) % Find minimal polynomial of e. em is in GF(2).

emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)

Это выход

em = GF(2) array.

Array elements =

     0     0     1     1     1


emr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     6
     7

Чтобы выяснить, какие элементы массива поля Галуа имеют один и тот же минимальный полином, используйте cosets функция.

Манипуляции с переменными Галуа

• Обзор разделов

• Определение, является ли переменная массивом полей Галуа

• Извлечение информации из массива полей Галуа

Обзор разделов.  В этом разделе описываются методы для манипулирования переменными Галуа или для передачи информации между массивами полей Галуа и обычными массивами MATLAB.

Определение, является ли переменная массивом полей Галуа.  Чтобы выяснить, является ли переменная массивом полей Галуа, а не обычным массивом MATLAB, используйте isa функция. Рисунок приведен ниже.

mlvar = eye(3);
gfvar = gf(mlvar,3);
no = isa(mlvar,'gf'); % False because mlvar is not a Galois array
yes = isa(gfvar,'gf'); % True because gfvar is a Galois array

Извлечение информации из массива полей Галуа.  Чтобы извлечь элементы массива, порядок поля или примитивный полином из переменной, которая является массивом полей Галуа, добавьте суффикс к имени переменной. В приведенной ниже таблице перечислены точные суффиксы, которые не зависят от имени переменной.

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

% Check that e solves its own minimal polynomial.
e = gf(6,4); % An element of GF(16)
emp = minpol(e); % The minimal polynomial, emp, is in GF(2).
empr = roots(gf(emp.x,e.m)); % Find roots of emp in GF(16).

% Check that the primitive element gf(2,m) is
% really a root of the primitive polynomial for the field.
primpoly_int = double(e.prim_poly);
mval = e.m;
primpoly_vect = gf(de2bi(primpoly_int,mval+1,'left-msb'),mval);
containstwo = roots(primpoly_vect); % Output vector includes 2.

Преобразование массива Галуа в двойной точности

a = gf([1,0])
b = double(a.x) %a.x is in uint16

MATLAB возвращает следующее:

a = GF(2) array.

Array elements =

           1           0


b =

     1     0

Полиномы скорости и недефолта

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

Механизм повышения скорости является файлом данных, userGftable.mat, которые некоторые вычислительные функции используют, чтобы избежать выполнения определенных расчетов неоднократно. Чтобы воспользоваться этим механизмом для комбинации порядка полей (m) и примитивный полином (prim_poly):

Функция пересматривает или создает userGftable.mat в текущую рабочую папку для включения данных, относящихся к комбинации порядка поля и примитивного полинома. После того, как вы первоначально инвестируете время, чтобы обратиться gftable, последующие расчеты с использованием этих значений m и prim_poly должен быть быстрее.

Чтобы увидеть, сколько gftable улучшает скорость ваших расчетов, вы можете окружить расчеты с tic и toc функций. См. gftable страница с описанием для примера.

Выбранная библиография для полей Галуа

Терминология поля Галуа

На протяжении всего этого раздела p является нечетным простым числом, а m является положительным целым числом.

Кроме того, этот документ использует несколько терминов, которые не используются последовательно в литературе. Принятые здесь определения появляются в van Lint [5].

Представление элементов полей Галуа

• Обзор разделов

• Экспоненциальный формат

• Полиномиальный формат

• Список всех элементов поля Галуа

• Неоднородность представлений

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

Элементы GF (p) могут быть представлены с помощью целых чисел от 0 до p-1.

Когда m меньше 2, GF (p^m) называется полем внутреннего абонента. Только целые числа не могут представлять элементы GF (p^m) прямым способом. Техническое вычислительное программное обеспечение MATLAB использует два основных соглашения для представления элементов GF (p^m): экспоненциальный формат и полиномиальный формат.

Экспоненциальный формат.  Этот формат использует свойство, что каждый ненулевой элемент GF (p^m) может быть выражено как A^c для некоторого целого числа c между 0 и p^m-2. Высшие степени не нужны, потому что теория полей Галуа подразумевает, что каждый ненулевой элемент GF (p^m) удовлетворяет уравнению x^q-1 = 1, где q = p^m.

Использование экспоненциального формата показано в таблице ниже.

Хотя -Inf - стандартное экспоненциальное представление нулевого элемента, все отрицательные целые числа эквивалентны -Inf при использовании в качестве входных параметров в экспоненциальном формате. Эта эквивалентность может быть полезной; для примера см. краткую строку кода в конце раздела «Примитив по умолчанию» Полиномы.

Полиномиальный формат.  Полиномиальный формат использует свойство, что каждый элемент GF (p^m) может быть выражен как полином в A с экспонентами от 0 до m-1 и коэффициентами в GF (p). В полиномиальном формате элемент

A(1) + A(2) A + A(3) A²   +... + A(m) A^m-1

представлен в MATLAB вектором

[A(1) A(2) A(3) ... A(m)]

Список всех элементов поля Галуа.  Некоторые функции поля Галуа в этом тулбоксе требуют аргумента, который перечисляет все элементы поля расширения GF (p^m). Это снова относительно конкретного примитивного элемента A GF (p^m). Правильный формат для списка элементов является форматом матрицы, имеющей p^m строки, по одной для каждого элемента поля. Матрица имеет m столбцов, по одному для каждого коэффициента степени A в полиномиальном формате, показанном в Полиномиальном Формате выше. Первая строка содержит только нули, потому что она соответствует нулевому элементу в GF (p^m). Если k находится между 2 и p^m, затем k-я строка задает полиномиальный формат элемента A^k-2.

Минимальный полином A помогает в расчете этой матрицы, потому что он рассказывает, как выразить A^m в терминах более низких степеней А. Пример, в таблице ниже перечислены элементы GF (3²), где A является корнем примитивного полинома 2 + 2x + x². Этот полином позволяет многократно использовать замену

A² = -2 - 2A = 1 + A

при выполнении расчетов в среднем столбце таблицы.

Пример

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

p = 3; m = 2;
% Use the primitive polynomial 2 + 2x + x^2 for GF(9).
prim_poly = [2 2 1];
field = gftuple([-1:p^m-2]',prim_poly,p);

gftuple Функция обсуждается более подробно в Преобразовании и Упрощении Форматов Элементов.

Неоднородность представлений.  Заданное поле имеет более одного примитивного элемента. Если два примитивных элемента имеют различные минимальные полиномы, то соответствующие матрицы элементов будут иметь свои строки в другом порядке. Если два примитивных элемента имеют одинаковый минимальный полином, то матрица элементов поля одинаковая.

Другие способы, которыми представления элементов не являются уникальными, возникают из уравнений, которые удовлетворяют элементы поля Галуа. Например, экспоненциальный формат 8 в GF (9) действительно аналогичен экспоненциальному формату 0, потому что A⁸ = 1 = A⁰ в ГФ (9). В качестве другого примера замена, упомянутая непосредственно перед таблицей Elements of GF ( 9), показывает, что полиномиальный формат [0 0 1] действительно аналогичен полиномиальному формату [1 1].

Примитивные полиномы по умолчанию

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

prim_poly = gfprimdf(m,p); % If m and p are already defined

формирует стандартное представление вектора-строки минимального полинома по умолчанию для GF (p^m).

Для примера команда ниже показывает, что примитивный полином по умолчанию для GF (9) является 2 + x + x², не полином, используемый в Списке Всех Элементов Поля Галуа.

poly1=gfprimdf(2,3);

poly1 =

     2     1     1

Чтобы сгенерировать список элементов GF (p^m) используя примитивный полином по умолчанию, используйте команду

field = gftuple([-1:p^m-2]',m,p);

Преобразование и упрощение форматов элементов

• Преобразование в простой полином формат

• Пример: Создание списка элементов поля Галуа

• Преобразование в простой экспоненциальный формат

Преобразование в простой полином формат.   gftuple функция производит простое полиномиальное представление элемента GF (p^m), заданное экспоненциальное представление или полиномиальное представление этого элемента. Это может быть полезно для генерации списка элементов GF (p^m) которые требуют другие функции.

Используя gftuple требует трех аргументов: один, представляющий элемент GF (p^m), один, указывающий примитивный полином, который должно использовать техническое вычислительное программное обеспечение MATLAB при вычислении выхода, и prime. Таблица ниже указывает, как gftuple ведет себя при задании первых двух аргументов в различных форматах.

Четыре примера, которые появляются в таблице выше, все производят один и тот же вектор  tp = [2, 1], но их различные входы gftuple соответствуют линиям таблицы. Каждый пример выражает тот факт, что A⁶ = 2 + A, где A является корнем (по умолчанию) примитивного полинома 2 + x + x² для GF (3²).

Пример

Этот пример показывает, как gfconv и gftuple объединить, чтобы умножить два элемента полиномиального формата GF (3⁴). Первоначально, gfconv умножает два полиномов, обрабатывая примитивный элемент, как если бы он был переменной. Это производит полином высокого порядка, который gftuple упрощает использование полиномиального уравнения, которое удовлетворяет примитивный элемент. Конечным результатом является самый простой полиномиальный формат продукта.

p = 3; m = 4;
a = [1 2 0 1]; b = [2 2 1 2];
notsimple = gfconv(a,b,p) % a times b, using high powers of alpha
simple = gftuple(notsimple,m,p) %Highest exponent of alpha is m-1

Ниже приведен выход.

notsimple =

     2     0     2     0     0     1     2


simple =

     2     1     0     1

Пример: Создание списка элементов поля Галуа.  Этот пример применяет функциональность преобразования к задаче генерации матрицы, в которой перечислены все элементы массива поля Галуа. Матрица, которая перечисляет все элементы поля, является входным параметром в функциях, таких как gfadd и gfmul. Переменные field1 и field2 ниже имеют формат, который ожидают такие функции.

p = 5; % Or any prime number
m = 4; % Or any positive integer
field1 = gftuple([-1:p^m-2]',m,p);

prim_poly = gfprimdf(m,p); % Or any primitive polynomial
% for GF(p^m)
field2 = gftuple([-1:p^m-2]',prim_poly,p);

Преобразование в простой экспоненциальный формат.  Та же функция gftuple также создает простое экспоненциальное представление элемента GF (p^m), заданное экспоненциальное представление или полиномиальное представление этого элемента. Чтобы получить этот выход, используйте синтаксис

[polyformat, expformat] = gftuple(...)

Формат входа и выход polyformat являются как в таблице Поведение gftuple в зависимости от формата первых двух входов. В сложение переменная expformat содержит простой экспоненциальный формат элемента, представленного в polyformat. Это самое простое в том смысле, что экспонента либо -Inf или число от 0 до p^m-2.

Пример

Чтобы восстановить экспоненциальный формат элемента 2 + A, который рассматривался в предыдущем разделе, используйте команды ниже. В этом случае polyformat содержит избыточную информацию, в то время как expformat содержит требуемый результат.

[polyformat, expformat] = gftuple([2 1],2,3)

polyformat =

     2     1

expformat =

     6

Этот выход появляется сначала, чтобы противоречить информации в таблице Elements of GF (9 ), но на самом деле он не делает. Таблица использует другой примитивный элемент; два плюс, что примитивный элемент имеет полиномиальный и экспоненциальный форматы, показанные ниже.

prim_poly = [2 2 1];
[polyformat2, expformat2] = gftuple([2 1],prim_poly,3)

Выходы ниже отражают информацию в нижней линии таблицы.

polyformat2 =

     2     1


expformat2 =

     7

Арифметика в полях Галуа

• Обзор разделов

• Арифметика в простых полях

• Арифметика в полях расширений

Обзор разделов.  Можно сложить, вычесть, умножить и разделить элементы полей Галуа с помощью функций gfadd, gfsub, gfmul, и gfdiv, соответственно. Каждая из этих функций имеет режим для простых полей и режим для полей внутренних линий.

Арифметика в простых полях.  Арифметика в GF (p) аналогична арифметической по модулю p. Функцииgfadd, gfmul, gfsub, и gfdiv принять два аргумента, которые представляют элементы GF (p) как целые числа от 0 до p-1. Третий аргумент задает p.

Пример: Таблица сложения для GF (5)

Приведенный ниже код создает таблицу сложения для GF (5). Если a и b находятся между 0 и 4, тогда элемент gfp_add(a+1,b+1) представляет сумму a+b в ГФ (5). Для примера, gfp_add(3,5) = 1 потому что 2 + 4 1 по модулю 5.

p = 5;
row = 0:p-1;
table = ones(p,1)*row;
gfp_add = gfadd(table,table',p)

Выходные выходы для этого примера следуют ниже.

gfp_add =

     0     1     2     3     4
     1     2     3     4     0
     2     3     4     0     1
     3     4     0     1     2
     4     0     1     2     3

Другие значения p создание таблиц для различных простых полей GF (p). Замена gfadd около gfmul, gfsub, или gfdiv приводит таблицу для соответствующей арифметической операции в GF (p).

Арифметика в полях расширения.  Те же арифметические функции могут добавить элементы GF (p^m) когда m > 1, но формат аргументов сложнее, чем в случае выше. В целом арифметика в полях расширений сложнее, чем арифметика в простых полях; смотрите работы, перечисленные в «Выбранной библиографии для полей Галуа», для получения дополнительной информации о том, как работают арифметические операции.

При работе в полях внутренних линий функции gfadd, gfmul, gfsub, и gfdiv используйте первые два аргумента, чтобы представлять элементы GF (p^m) в экспоненциальном формате. Третий аргумент, который требуется, перечисляет все элементы GF (p^m) как описано в Списке всех элементов поля Галуа. Результат в экспоненциальном формате.

Пример: Таблица сложения для GF (9)

Приведенный ниже код создает таблицу сложений для GF (3²), используя экспоненциальные форматы относительно корня примитивного полинома по умолчанию для GF (9). Если a и b находятся между -1 и 7, тогда элемент gfpm_add(a+2,b+2) представляет сумму A^a А^b в ГФ (9). Для примера, gfpm_add(4,6) = 5 потому что

A² + А⁴ = A⁵

Использование четвертой и шестой строк матрицы field, можно проверить, что

A² + А⁴ = (1 + 2A) + (2 + 0A) = 3 + 2A = 0 + 2A = A⁵ по модулю 3.

p = 3; m = 2; % Work in GF(3^2).
field = gftuple([-1:p^m-2]',m,p); % Construct list of elements.
row = -1:p^m-2;
table = ones(p^m,1)*row;
gfpm_add = gfadd(table,table',field)

Ниже приведен выход.

gfpm_add =

  -Inf     0     1     2     3     4     5     6     7
     0     4     7     3     5  -Inf     2     1     6
     1     7     5     0     4     6  -Inf     3     2
     2     3     0     6     1     5     7  -Inf     4
     3     5     4     1     7     2     6     0  -Inf
     4  -Inf     6     5     2     0     3     7     1
     5     2  -Inf     7     6     3     1     4     0
     6     1     3  -Inf     0     7     4     2     5
     7     6     2     4  -Inf     1     0     5     3

Другие значения p и m создание таблиц для различных полей расширения GF (p^m). Замена gfadd около gfmul, gfsub, или gfdiv приводит таблицу для соответствующей арифметической операции в GF (p^m).

Полиномы над простыми полями

• Обзор разделов

• Косметические изменения полиномов

• Полиномиальная арифметика

• Характеристика полиномов

• Корни полиномов

Обзор разделов.  Полином над GF (p) является полиномом, коэффициенты которого являются элементами GF (p). Программное обеспечение Communications Toolbox обеспечивает функции для

Косметические изменения полиномов.  Чтобы отобразить традиционно форматированный полином, который соответствует вектору-строке, содержащей коэффициенты, используйте gfpretty. Чтобы обрезать полином путем удаления всех членов с нулевым коэффициентом, которые имеют степени выше, чем степень полинома, используйте gftrunc. Для примера,

polynom = gftrunc([1 20 394 10 0 0 29 3 0 0])
gfpretty(polynom)

Ниже приведен выход.

polynom =

     1    20   394    10     0     0    29     3


                                   2       3       6      7
                   1 + 20 X + 394 X  + 10 X  + 29 X  + 3 X

Полиномиальная арифметика.  Функции gfadd и gfsub сложить и вычесть, соответственно, полиномы над GF (p). gfconv функция умножает полиномы на GF (p). gfdeconv функция делит полиномы в GF (p), производя частный полином и оставшийся полином. Для примера команды ниже показывают, что 2 + x + x² умножить 1 + x по полю GF (3) на 2 + 2x² + x³.

a = gfconv([2 1 1],[1 1],3)
[quot, remd] = gfdeconv(a,[2 1 1],3)

Ниже приведен выход.

a =

     2     0     2     1


quot =

     1     1

remd =

     0

Ранее обсуждавшиеся функции gfadd и gfsub сложить и вычесть, соответственно, полиномы. Поскольку он использует вектор коэффициентов, чтобы представлять полином, MATLAB не различает добавление двух полиномов и добавление двух векторов-строк элементарно.

Характеристика полиномов.  Учитывая полином над GF (p), gfprimck функция определяет, является ли она неприводимой и/или примитивной. По определению, если он примитивен, то он неприводим; однако обратное не обязательно верно. gfprimdf и gfprimfd функции возвращают примитивные полиномы.

Задан элемент GF (p^m), gfminpol функция вычисляет свой минимальный полином над GF (p).

Пример

Для примера, код ниже отражает неснижаемость всех минимальных полиномов. Однако минимальный полином непримитивного элемента не является примитивным полиномом.

p = 3; m = 4;
% Use default primitive polynomial here.

prim_poly = gfminpol(1,m,p);
ckprim = gfprimck(prim_poly,p);
% ckprim = 1, since prim_poly represents a primitive polynomial.

notprimpoly = gfminpol(5,m,p);
cknotprim = gfprimck(notprimpoly,p);
% cknotprim = 0 (irreducible but not primitive)
% since alpha^5 is not a primitive element when p = 3.

ckreducible = gfprimck([0 1 1],p);
% ckreducible = -1 since the polynomial is reducible.

Корни полиномов.  Учитывая полином над GF (p), gfroots функция находит корни полинома в подходящем поле расширения GF (p^m). Существует два способа сообщить MATLAB степень m поля расширения GF (p^m), как показано в следующей таблице.

Пример: Корни полинома в GF (9)

Код ниже находит корни полинома 1 + x² + x³ в GF (9) и затем проверяет, что они действительно являются корнями. Экспоненциальный формат элементов GF (9) используется повсеместно.

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

Этот выход показывает, что A⁰ (что равняется 1), A⁵, и A⁷ являются корнями.

roots =

     0
     5
     7


answer =

  -Inf  -Inf  -Inf

Смотрите страницу с описанием для gfroots чтобы увидеть как gfroots может также предоставить вам полиномиальные форматы корней и список всех элементов поля.

Другие функции поля Галуа

Смотрите онлайн- страницы с описанием для получения информации об этих других функциях поля Galois в программном обеспечении Communications Toolbox:

Выбранная библиография для полей Галуа