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

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

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

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

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

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

Непрямой алгоритм CRC

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

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

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

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

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

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

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

Предположим, что входной кадр [1 1 0 0 1 1 0]', соответствующий многочлену M = x6 + x 5 + x2 + x, и ^{полином генератора} является P = x3 + x2 + 1, степени r ⁼ 3. По многочленовому  делению, М*x3 = (x6 + x3 + x)*P + x. Остаток равен R = x, поэтому контрольная сумма равна [0 1 0]'. Слева добавляется дополнительный 0, чтобы контрольная сумма имела длину 3.

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

где

Входной блок сообщения - $${}_{\mathrm{m0}},{}_{\mathrm{m1}},\text{.}\mathrm{..,}\text{mk}{}_{-1}$$

Выходное кодовое слово - $${}_{\mathrm{c0}},{}_{\mathrm{c1}},\mathrm{...,}{}_{\mathrm{cn}}\underset{}{\underset{}{{-}_{\mathrm{}}1{=}_{\mathrm{}}\mathrm{m0,}\text{m1}\text{,}.{.}_{\mathrm{.,}\mathrm{}}}}\underset{.}{\underset{.}{{}_{\mathrm{}}mk{}_{\mathrm{-}}\text{1}\mathrm{,\; ︸}{\mathrm{Xd0}}_{,d1\mathrm{,}}}}$$., dn−k−1︸Y

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Можно отобразить время выборки сигналов в модели. На вкладке «Отладка» разверните узел «Информационные наложения». В разделе «Образец времени» выберите «Цвета». Кроме того, можно присоединить блоки зонда (Simulink) к соединительным линиям, чтобы оценить время выборки, буферизацию и задержки.

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

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

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

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

После настройки блоков кодирования несколько советов помогут правильно разместить их в модели:

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

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

Откройте модель путем ввода doc_rscoding в командной строке MATLAB. Для построения модели соберите и настройте следующие блоки:

Подключите блоки, как показано на предыдущем рисунке. На вкладке Моделирование (Simulation) в разделе Моделирование (Simulate) задайте для параметра Время остановки (Stop time) значение 500. Раздел «Моделирование» отображается на нескольких вкладках.

Можно отобразить векторную длину сигналов в модели. На вкладке «Отладка» разверните узел «Информационные наложения». В разделе «Сигналы» выберите «Размеры сигнала».

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

При запуске модели создаются следующие изображения области. Число ошибок на графике зависит от начального начального значения, используемого в блоке генератора случайных чисел. Можно настроить диапазон осей, точно соответствующий диапазону первой области. Щелкните правой кнопкой мыши область печати во второй области и выберите «Свойства конфигурации». На вкладке Отображение (Display) отрегулируйте пределы осей.

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

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

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

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

Общие коды линейных блоков

Кодирование сообщения с использованием общего линейного блочного кода требует матрицы генератора. Декодирование кода требует матрицы генератора и, возможно, таблицы истинности. Для использования блоков Двоичный линейный кодер (Binary Linear Encoder) и Двоичный линейный декодер (Binary Linear Decoder) необходимо понимать параметры матрицы генератора и таблицы истинности коррекции ошибок.

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

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

Блок двоичного линейного декодера позволяет указать таблицу декодирования в параметре таблицы истинности исправления ошибок. Представление таблицы декодирования в виде матрицы с N столбцами и ^2N-K строками. Каждая строка дает вектор коррекции для одного принятого вектора кодового слова.

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

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

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

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

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

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

Коды хэммминга

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

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

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

Коды BCH

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

Коды BCH с узким кодом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На первом этапе декодер добавляет стирание, обозначенное Е, во вторую позицию четности кодового слова. Это соответствует вектору прокола 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.

Дополнительные сведения см. в примере кодирования Рида-Соломона со стиранием, проколами и укорочением MATLAB или в примере кодирования Рида-Соломона со стиранием, проколами и укорочением в 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 - ^Ab) ( X - ^Ab + 1).. . (X ^{- Ab} + 2t-1), где A - примитивный элемент для соответствующего поля Галуа, а b и t - целые числа. Дополнительные сведения об этом выражении см. на страницах ссылок функций.

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

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

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

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

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

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

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

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

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

Для обработки сверточных кодов используйте блоки сверточного кодера, декодера Витерби и/или декодера APP в сверточном поддиапазоне. Если параметр маски необходим и в кодере, и в декодере, используйте одно и то же значение в обоих блоках.

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

Дополнительные сведения об этих представлениях см. в разделах Полиномиальное описание сверточного кода и Решетчатое описание сверточного кода.

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

Чтобы использовать описание полинома с блоками сверточного кодера, декодера Витерби или декодера APP, используйте функцию утилиты poly2trellis из панели инструментов связи. Эта функция принимает полиномиальное описание и преобразует его в решетчатое описание. Например, следующая команда вычисляет решетчатое описание кодера, длина ограничения которого равна 5, а полиномы генератора - 35 и 31:

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

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

poly2trellis(5,[35 31]);

в поле параметра структуры решетки.

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

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

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

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

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

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

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

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

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

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

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

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

Использовать решетчатую структуру для сверточного кодера с обратной связью со скоростью 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]

Создание случайных двоичных данных. Сверточное кодирование данных с использованием указанной решетчатой структуры. Декодирование кодированных данных с использованием алгоритма Витерби с заданной решетчатой структурой, 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. Он использует квантователь и блок декодера Витерби для выполнения декодирования с мягким решением. Для открытия модели введите doc_softdecision в командной строке MATLAB. Описание модели см. в разделе Обзор моделирования.

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

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

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

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

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

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

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

Сопоставление полученных данных

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

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

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

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

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

Если для параметра Тип решения установлено значение Soft Decisionблок декодера Витерби требует входных значений от 0 до ^2b-1, где b - параметр числа битов мягкого решения. Блок интерпретирует 0 как наиболее уверенное решение, что бит кодового слова является 0, и интерпретирует ^2b-1 как наиболее уверенное решение, что бит кодового слова является 1. Значения между этими крайностями представляют собой менее уверенные решения. В следующей таблице перечислены интерпретации восьми возможных входных значений для этого примера.

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

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

Оценка глубины отслеживания

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

K - количество входных символов, N - количество выходных символов, а PuncurePattern - вектор прокола.

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

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

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

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

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

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

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

Дизайн a Кодирующее устройство Rate-2/3 Feedforward Используя MATLAB

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

Определение параметров кодирования.   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 с использованием Simulink

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

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

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

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

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

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

Для открытия завершенной модели введите doc_convcoding в командной строке MATLAB. Для построения модели соберите и настройте следующие блоки:

Подключите блоки, как показано на предыдущем рисунке. На вкладке Моделирование (Simulation) в разделе Моделирование (Simulate) задайте для параметра Время остановки (Stop time) значение inf. Раздел «Моделирование» отображается на нескольких вкладках.

Примечания к модели.  Можно отобразить размер матрицы сигналов в модели. На вкладке «Отладка» разверните узел «Информационные наложения». В разделе «Сигналы» выберите «Размеры сигнала».

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

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

При выполнении модели выводится три номера: частота ошибок, общее количество ошибок и общее количество сравнений, которые блок вычисления частоты ошибок выполняет во время моделирования. (Первые два числа изменяются в зависимости от начальных значений в блоках Bernoulli Binary Generator и Binary Symmetric Channel.) Моделирование останавливается после 100 ошибок, поскольку для параметра «Целевое количество ошибок» установлено значение 100 в блоке «Расчет частоты ошибок». Частота ошибок намного меньше, чем 0.02, вероятность ошибки в блоке двоичного симметричного канала.

Проколоть сверточный код с помощью MATLAB

В этом примере обрабатывается проколотый сверточный код. Она начинается с генерации 30000 случайных битов и их кодирования с использованием сверточного кодера скорости 3/4 с шаблоном прокола [1 1 1 0 0 1]. Результирующий вектор содержит 40000 битов, которые отображаются в значения -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

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

Для реализации этого кодера установите параметр структуры решетки в блоке сверточного кодера в значение poly2trellis(5, [37 33], 37). Эта настройка соответствует

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

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

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

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

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

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

• Обзор моделирования

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

• Сопоставление полученных данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если для параметра Тип решения установлено значение Soft Decisionблок декодера Витерби требует входных значений от 0 до ^2b-1, где b - параметр числа битов мягкого решения. Блок интерпретирует 0 как наиболее уверенное решение, что бит кодового слова является 0, и интерпретирует ^2b-1 как наиболее уверенное решение, что бит кодового слова является 1. Значения между этими крайностями представляют собой менее уверенные решения. В следующей таблице перечислены интерпретации восьми возможных входных значений для этого примера.

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

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

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

В этом случае значение задержки приема равно значению глубины отслеживания (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 может различаться, поскольку моделирование включает случайные числа.

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

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

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

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

Для открытия модели введите 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 будет выполнять кодирование с учетом выбранной длины блока и решетки.

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

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

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

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

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

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

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

Используйте MATLAB для создания сообщений и кодовых слов в двоичном векторном формате.  Ваши сообщения и кодовые слова могут принимать форму векторов, содержащих 0 и 1. Например, сообщения и коды могут выглядеть как 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] циклических, хэмминговых и родовых линейных блочных кодов. В таблице ниже перечислены элементы и методы кодирования, для которых они наиболее актуальны .

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

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

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

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

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

Примеры

В приведенной ниже команде parmat является матрицей проверки четности и genmat является генераторной матрицей для кода Хэмминга, в которой [n, k ] = [^23-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 функция упоминается ниже в Полиноме генератора (Generator Polynomial).

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) многочлена ^xn-1. Ван Линт [5] объясняет, как генераторный многочлен определяет циклический код.

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

genpoly = cyclpoly(7,3)

genpoly =

     1     0     1     1     1

обнаруживает, что один допустимый полином генератора для [7,3] циклического кода равен 1 + ^x2 + ^x3 + ^x4.

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

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

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

В приведенном ниже сценарии показано, как использовать таблицу декодирования Хэмминга для исправления ошибки в полученном сообщении. 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. В этом разделе рассматривается использование этих функций для создания и декодирования общих линейных блочных кодов, циклических кодов и кодов Хэмминга.

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

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

кодирует информацию в msg с использованием [n,k] код матрицы генератора genmat определяет. /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). /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

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

Открыть эту модель путем ввода doc_hamming в командной строке MATLAB. Для построения модели соберите и настройте следующие блоки:

Соедините блоки, как показано на предыдущем рисунке. Можно отобразить векторную длину сигналов в модели. На вкладке «Отладка» разверните узел «Информационные наложения». В разделе «Сигналы» выберите «Размеры сигнала». После обновления диаграммы при необходимости нажмите Ctrl + D для компиляции модели и проверки статистики ошибок.

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

Уменьшение частоты ошибок с помощью кода хэммминга

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

Для открытия полной версии модели введите doc_hamming по запросу MATLAB.

Построение модели кода Хэмминга

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

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

Использование блоков кодера и декодера Хэмминга

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

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

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

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

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

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

Маркировка экранного блока

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

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

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

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

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

Чтобы получить меньшую частоту ошибок для той же вероятности ошибки, попробуйте использовать код Хэмминга с большими параметрами. Для этого измените параметры Codword length и Message length в диалоговых окнах блоков Hamming Encoder и Hamming Decoder. Необходимо также внести соответствующие изменения в параметры блока двоичного генератора Бернулли и блока двоичного симметричного канала.

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

В модели можно отображать размеры фреймов данных в различных частях. На вкладке «Отладка» разверните узел «Информационные наложения». В разделе «Сигналы» выберите «Размеры сигнала». Линия, выходящая из блока двоичного генератора Бернулли, помечена [4x1], указывая, что его выход состоит из векторов столбцов размера 4. Поскольку блок кодера Хэмминга использует код [7,4], он преобразует кадры размера 4 в кадры размера 7, поэтому его выходной сигнал помечается [7x1].

Добавление области в модель

Чтобы отобразить ошибки канала, вызванные блоком «Бинарный симметричный канал», добавьте в модель блок «Область». Это хороший способ проверить правильность работы модели. Пример, показанный на следующем рисунке, показывает, куда вставить блок «Область» в модель.

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

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

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

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

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

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

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

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

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

По завершении наблюдения за ошибками выберите Моделирование > Остановить.

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

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

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

Ниже приведен пример представления слов для кода BCH [15, 11].

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

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

Темы:

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

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

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

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 Decoder Системный объект ведет себя, когда шум является чрезмерным, см. аналогичное обсуждение кодов Рида-Соломона в разделе Чрезмерный шум в кодовых словах Рида-Соломона.

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

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

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

Расчет синдрома.  Для кодов с узким смыслом 2t членов $$S(z$$) вычисляются путем оценки принятого кодового слова при последовательных степенях α (примитивного элемента поля) от 0 до 2t-1. Другими словами, если предположить одноосновное индексирование кодовых слов $$C($$z) и $$\mathrm{синдромного\; многочлена}S$$(z), и что кодовые слова имеют $${\mathrm{вид}}_{\mathrm{}}\text{ [}{}_{\mathrm{c1}}\mathrm{c1}\text{ ...}{}_{}$$cN], то каждый $${\mathrm{член}}_{}$$Si $$\mathrm{из\; S}$$(z) задается как

Расчет полинома локатора ошибок.  Полином локатора ошибок Λ (z) находится с помощью алгоритма Берлекампа. Полное описание этого алгоритма приведено в [2], но мы суммируем алгоритм следующим образом.

Мы определяем следующие переменные.

На следующей диаграмме показана итеративная процедура (то есть алгоритм Берлекампа), используемая для поиска Λ (z).

Расчет полинома вычислителя ошибок.  Многочлен-вычислитель ошибок, $$\Lambda (z$$), является просто сверткой Λ (z) $$иS$$(z).

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

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

r = rsgenpoly(15,13)

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

Array elements =

     1     6     8

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

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

Генератор многочленов, которые rsgenpoly произведения имеют вид (X - ^Ab) ( X - ^Ab + 1).. . (X ^{- Ab} + 2t-1), где b - целое число, A - корень примитивного многочлена для поля Галуа, t -(n-k)/2. Значение по умолчанию b равно 1. Выходные данные 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.

Создание и декодирование кодов Рида-Соломона

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

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

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

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

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

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

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

Этот пример также показывает, что соответствующие синтаксисы 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

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

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 - ^Ab) ( X - ^Ab + 1).. . (X ^{- Ab} + 2t-1), где A - примитивный элемент для соответствующего поля Галуа, а b и t - целые числа. Дополнительные сведения об этом выражении см. на страницах ссылок функций.

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

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

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

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

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

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

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

На первом этапе декодер добавляет стирание, обозначенное Е, во вторую позицию четности кодового слова. Это соответствует вектору прокола 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]:

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

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

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

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

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

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

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

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

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

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

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

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

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

Для некоторых операций с массивами полей Galois требуется несколько аргументов. Если указать один аргумент, который является массивом полей Galois, а другой - обычным массивом MATLAB, MATLAB интерпретирует оба параметра как массивы полей Galois в одном поле. Он неявно вызывает 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

Выходные данные показывают значения массивов полей Galois a и b. Каждая выходная секция указывает

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

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

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, оценивается на примитивном элементе поля. m-кортеж коэффициентов многочлена соответствует двоичному представлению целого числа от 0 до 2^m.

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

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

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 представляет примитивный элемент из-за соответствия между

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

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

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

Обсуждение в «Как целые числа соответствуют элементам поля Галуа» относится к примитивному элементу, который является корнем примитивного многочлена поля. При использовании 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, которое в свою очередь соответствует многочлену ^D4 + ^D3 + 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 для оптимизации вычислений с использованием примитивного многочлена 13, не используемого по умолчанию.

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

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

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

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

• Пример: Подразделение

• Пример: Возведение в степень

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

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

Умножение и деление многочленов на поле Галуа см. в разделе Сложение и вычитание многочленов.

Пример: Сложение и вычитание.  Приведенный ниже код добавляет два массива полей Galois для создания таблицы сложения для 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). Эквивалентно, элемент ^A2 + A плюс элемент A + 1 равен ^{элементу} A2 + 1. Эквивалентность возникает из двоичного представления 6 как 110, 3 как 011 и 5 как 101.

Таблица вычитания, которую можно получить путем замены + около -, совпадает с addtb. Это объясняется тем, что вычитание и сложение являются идентичными операциями в поле характеристики 2. Фактически нули вдоль главной диагонали 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. Это верно, поскольку 5 представляет полиномиальное выражение A2 + 1, а ¹ + (A2 + 1) в GF ⁽16) равно A2. Кроме того, целое число, которое представляет A2 полиномиального ^{выражения}, равно 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 является корнем полинома примитива. .^ оператор экспонирует каждый элемент массива независимо.

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 и получить логический массив. Некоторые важные типы тестов - тестирование на равенство двух массивов полей Галуа и тестирование на ненулевые значения в массиве полей Галуа.

Проверка на равенство.  Для сравнения соответствующих элементов двух массивов полей 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, за исключением того, что они рассматривают только нижележащие элементы массива при игнорировании информации о том, в каком поле Galois находятся элементы. Примеры приведены ниже.

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

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

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

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

Основные манипуляции с массивами полей Галуа.  Основные операции с массивами полей Galois приведены в таблице ниже. Функциональные возможности этих операций аналогичны операциям 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.

Основные сведения о массивах полей Galois.  Можно определить длину вектора Галуа или размер любого массива полей Галуа, используя length и size функции. Функциональные возможности массивов полей Galois аналогичны функциям операций 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 функция. Однако для массива полей Galois следует использовать 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

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

Результаты синтаксиса в таблице зависят от характеристик массива полей Галуа 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).

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

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

• Фильтрация

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

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

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

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

Другая информация о соответствующих операциях для обычных реальных векторов содержится в документации по 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 в GF (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.

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

Во всех случаях преобразуемый вектор должен быть вектором Галуа длиной ^2m-1 в поле GF (^2m). Следующий пример иллюстрирует использование этих функций. Вы можете проверить, используя 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)

представляет многочлен ^Ax3 + ^1x2 + 0x + (A + 1), где

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

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

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 имеют одинаковое однозначное представление во всех областях характеристики 2. Чтобы найти корни двоичного многочлена в поле расширения, примените 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 (^2m) является многочленом с ненулевым двоичным коэффициентом наименьшей степени, имеющим этот элемент в качестве корня в GF ⁽2m). Чтобы найти минимальный полином элемента или вектор столбца элементов, используйте minpol функция.

Код ниже обнаруживает, что минимальный многочлен gf(6,4) является ^D2 + 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 функция.

Манипулирование переменными Галуа

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

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

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

Раздел Обзор.  В этом разделе описываются методы управления переменными Galois или передачи информации между массивами полей Galois и обычными массивами 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

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

Код ниже иллюстрирует использование этих суффиксов. Определение 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

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

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

Механизмом увеличения скорости является файл данных, 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 (^pm) называется полем расширения. Только целые числа не могут представлять элементы GF ⁽pm) простым способом. Техническое вычислительное программное обеспечение MATLAB использует два основных условных обозначения для представления элементов GF (pm): экспоненциальный формат и полиномиальный формат.

Экспоненциальный формат.  Этот формат использует свойство, согласно которому каждый ненулевой элемент GF (^pm) может быть выражен как ^Ac для некоторого целого числа c между 0 и ^pm-2. Более высокие экспоненты не нужны, поскольку теория полей Галуа подразумевает, что каждый ненулевой элемент GF ⁽pm) удовлетворяет уравнению ^xq-1  = 1, где q = pm.

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

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

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

A(1) + A(2)  + A(3) ^A2 + ... + A(m) ^Am-1

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

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

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

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

^A2 = -2 - 2 А = 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, потому что ^A8  = 1 = ^A0 в GF (9). В качестве другого примера подстановка, упомянутая непосредственно перед таблицей Elements of GF (9), показывает, что полиномиальный формат [0 0 1] действительно тот же, что и полиномиальный формат [1 1].

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

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

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

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

Например, приведенная ниже команда показывает, что примитивный многочлен по умолчанию для GF (9) - это 2 + x + ^{x2, а} не многочлен, используемый в списке всех элементов поля Галуа.

poly1=gfprimdf(2,3);

poly1 =

     2     1     1

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

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

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

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

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

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

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

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

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

Пример

В этом примере показано, как gfconv и gftuple объединение для умножения двух элементов полиномиального формата GF (³⁴). Изначально ,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 (^pm), задаваемое либо экспоненциальным представлением, либо полиномиальным представлением этого элемента. Для получения выходных данных используйте синтаксис

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

Формат ввода и выходные данные polyformat как в таблице Поведение gftuple в зависимости от формата первых двух входов. Кроме того, переменная expformat содержит простейший экспоненциальный формат элемента, представленного в polyformat. Проще всего в том смысле, что экспонента либо -Inf или число от 0 до ^pm-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 в GF (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 (^pm) при m > 1, но формат аргументов сложнее, чем в случае выше. В общем случае арифметика в полях расширения сложнее, чем арифметика в простых полях; подробные сведения о работе арифметических операций см. в разделе Избранная библиография для Галуа Филдс .

При работе в полях расширения функции gfadd, gfmul, gfsub, и gfdiv используйте первые два аргумента для представления элементов GF (^pm) в экспоненциальном формате. Третий аргумент, который требуется, перечисляет все элементы GF ⁽pm), как описано в списке всех элементов поля Галуа. Результат в экспоненциальном формате.

Пример: Таблица добавления для GF (9)

Приведенный ниже код создает таблицу сложения для GF (³²), используя экспоненциальные форматы относительно корня примитивного многочлена по умолчанию для GF (9). Еслиa и b находятся между -1 и 7, затем элемент gfpm_add(a+2,b+2) представляет собой сумму ^Aa и ^Ab в GF (9). Например ,gfpm_add(4,6) = 5 потому что

^A2 + ^A4 = ^A5

Использование четвертой и шестой строк матрицы field, вы можете проверить, что

^A2 + ^A4 = (1 + 2A) + (2 + 0A) = 3 + 2A = 0 + 2A = ^A5 по модулю 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 + ^x2 умножить  на 1 + x над полем GF (3) равно 2 + ^2x2  + x3.

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 (^pm), 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 (^pm). Существует два способа указания MATLAB степени m поля расширения GF ⁽pm), как показано в следующей таблице.

Пример: Корни полинома в GF (9)

Код ниже находит корни многочлена 1 + ^x2 + ^x3 в 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

Выходные данные показывают, что ^A0 (что равно 1), ^A5 и ^A7 являются корнями.

roots =

     0
     5
     7


answer =

  -Inf  -Inf  -Inf

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

Другие функции поля Галуа

Для получения информации об этих других функциях поля Galois в ПО Communications Toolbox см. интерактивные справочные страницы:

Избранная библиография для Галуа Филдс