Выбор образующего полинома

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

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

1.Степень образующего полинома должна быть не меньше числа проверочных символов r

2. Любой многочлен g(х) степени (n-к), который делит без ос­татка двучлен X n +1 может быть порождающим многочленом (n, к) циклического кода.

3. Образующий полином должен быть как можно более корот­ким.

4. Число ненулевых членов образующею полинома должно быть не меньше d_мин.

Поскольку в циклическом коде опознавателями ошибок явля­ются остатки от деления, то Р(х) должен обеспечивать требуемое число разлитых остатков. Обнаруживающая способность цикличе­ского кода определяется не только степенью обнаруживающего по­линома. но и числом его членов.

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

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

Не всякий многочлен степени r, входящий в разложение данно­го двучлена, может быть использован для образования нужного (n, k)-кода.

Чтобы выяснить, какое из произведений может быть использовано в качестве образующего полинома, необходимо для каждого из них по­строить так называемую дополнительную матрицу. Эта матрица строит­ся путем деления циклических сдвигов единицы с приписанными справа нулями на соответствующее произведение полиномов. При построении дополнительной матрицы С_r,k. по выбранному полиному необходимо также учитывать количество строк в цикле чередования проверочных разрядов и вес каждой строки (количество единиц).

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

Боуз и Чоудхурн показали, что для любых, целых положитель­ных чисел m и t_и существует циклический код элементности

с кодовым расстоянием

При этом число проверочных символов r не превышает величи­ны mt_u т.е.

r 2^ m +1= x n +1=x 15 +1.

Можно показать, что в разложение двучлена х 15 +1 в качестве сомножителей старшей степени входят полиномы Р₁(х 4 )=х 4 +х+1 —> 10011; Р₂(х 4 )=х 4 +х 3 +1->11001; Р₃(х 4 )=х 4 +х 3 +х 2 +x+1->11111. В учебнике (таблица 5.1) приведены образующие (примитивные) полиномы до 10-й степени.

Из трех возможных парных произведений полиномов четвертой степени получим три полинома восьмой степени r=8

Чтобы выяснить, какой из трех полиномов восьмой степени может быть использован в качестве образующего, найдем для каж­дого из них дополнительную матрицу С_8.7— (к=15-8=7). Делением единицы с приписанными справа нулями и ее циклических сдвигов на 111010001 10001011 и 110111011 находим соответственные до­полнительные матрицы

Для получения возможности исправления двойных ошибок до-полнигеяьные матрицы должны выбираться таким образом, чтобы вес м> каждой строки порождающей матрицы был не менее пяти единиц d_мин.>=2t_u+1

Так как каждая строка единичной матрицы Е- имеет вес равный единице, вес любой строки дополнительной матрицы должен быть не менее четырех единиц. Это требование, будет выполнено, если в каче­стве образующего полинома для построения циклического (15, 7)-кода выбрать одно из двух произведений: Р₁(х 4 )Рз(х 4 ) или Р₂(х 4 )Рз(х 4 )=

В третьей дополнительной матрице С_8.7 из семи строк третья, четвертая и пятая не обладают требуемым весом. Поэтому произве­дение Р₁(х 4 )Р2(х 4 ) не может быть использовано в качестве образую­щего полинома для построения циклического (.15, 7)-кода.

Источник

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

Что это такое

Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

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

Полиномиальная арифметика

Для тех, кто это подзабыл, приведем пример на деление.

Пример 1

Напомним также модульную арифметику многочленов. Многочлены называются сравнимыми по модулю многочлена p(x), если их разность делится на p(x) нацело. Поэтому для получения f(x)(mod p(x)) вам нужно просто разделить f(x) на p(x) и взять остаток от деления. Заметим, что если степень f(x) меньше степени p(x), то результатом будет просто f(x)

Пример 2

Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n-1 на многочлен «x» и нахождения остатка от деления на x n + 1.

Пример 3

Порождающий многочлен

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

Tеорема

Пример 4

Соответствующее кодовое слово[011010111100010]. Итак, сообщение [0110110] кодировано в слово [011010111100010].

Алгоритм декодирования

Пример 4 (прод.)

Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять s i (x) = x i (x 2 + x 6 + x 8 )(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).

s 1 = xs(x)(mod g(x)) = (x 3 + x 7 + x 9 )(mod g(x)) = x 3 + x 4 + x 5 + x 6 + x 7

s 2 = x 2 s(x)(mod g(x)) = (x 4 + x 8 + x 10 )(mod g(x)) = 1 + x + x 2 + x 5

s 3 = x 3 s(x)(mod g(x)) = (x 5 + x 9 + x 11 )(mod g(x)) = x + x 2 + x 3 + x 6

s 4 = x 4 s(x)(mod g(x)) = (x 6 + x 10 + x 12 )(mod g(x)) = x 2 + x 3 + x 4 + x 7

s 5 = x 5 s(x)(mod g(x)) = (x 7 + x 11 + x 13 )(mod g(x)) = 1 + x 3 + x 5 + x 6 + x 7

s 6 = x 6 s(x)(mod g(x)) = (x 8 + x 12 + x 14 )(mod g(x)) = x + 1

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким

(x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 ) + (x 10 + x 9 ) =

x + x 2 + x 4 + x 6 + x 7 + x 8 + x 9 + x 13

Этот многочлен соответствует вектору [011010111100010]. Чтобы восстановить само сообщение нам надо разделить кодовое слово на ПМ g(x) и получить

значит сообщение было [0110110].

IV. Размерность, порождающая и проверочная матрицы

c 1 (x) c 2 (x) = a 1 (x)g(x)a 2 (x)h(x) = a 1 (x)a 2 (x)f(x) = 0 (mod f(x)),

Рассмотрим два вектора:

и их произведение (вернее, соответствующих многочленов)

для каких-то c i из F. Свободный член произведения

т.к x n = 1 (mod f(x)). Теперь c 0 можно записать как скалярное произведение

где b’ теперь вектор, связанный с x n-t b(x). По отношению к b(x), b’ это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.

Коэффициент при x 2 будет a (b 2 b 1 b 0 ). Этот вектор b’ получен из b сдвигом на 3 ( = 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 ( = 1 + 1) позиции влево, что дает (b 2 b 0 b 1 ) и изменением порядка следования (b 1 b 0 b 2 ).

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

Перепишем колонки G’ в обратном порядке, получим порождающую матрицу для C perp (она же проверочная для исходного кода)

Нетрудно проверить, что GH T = 0.

Заметим, что h R (x) = x k h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.

V. Синдромы и охота на ошибки

где deg(r i (x)) i (x) = 0. Then

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

x 3 = (1)(x 3 + x + 1) + (1+ x)
x 4 = (x)(x 3 + x + 1) + (x + x 2 )
x 5 = (x 2 + 1)(x 3 + x + 1) + (1 + x + x 2 )
x 6 = (x 3 + x + 1)(x 3 + x + 1) + (1 + x 2 ).

Порождающая матрицаЗаметим, что строки R как раз остатки от деления.

Если разделить r(x) на g(x), то получим

r(x) = (x 3 + 1)g(x) + (x + x 2 ),

Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0’s и 6 > k = 4, исправляются все единичные ошибки..

Пример : g(x) = 1 + x 4 + x 6 + x 7 + x 8 порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили

r = (1100 1110 1100 010)

r(x) = (x + x 2 + x 4 + x 5 )g(x) + (1 + x 2 + x 5 + x 7 ).

Источник

9. Циклические коды. Образующий полином.

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

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

Представление кодовой комбинации в виде полинома.

Q(x)=111111=x 5 +x 4 +x 3 +x 2 +x 1 +x 0

x_i – двоичный разряд. x 1 =x, x 0 =1

Если какой-либо разряд x_i = 0 в составе полинома, то его опускают.

Q(x)=1100110=x 6 +x 5 +x 2 +x

Образующий полином – это полином, который является простым числом: (11)₁₀, (13)₁₀, (17)₁₀, (19)₁₀ и т.д. Он выбирается заранее как делитель, позволяющий выполнять обнаружение и исправление ошибки.

P(x)=(11)₁₀=(1011)₂=x 3 +x+1 Степень образующего полинома – к. (к=3)

Операция деления полинома на полином.

Деление сходно с алгебраическим, но есть отличие:

операция вычитания заменяется суммированием по модулю 2;

деление заканчивается, если наивысшая степень у остатка меньшей таковой у делителя;

интерес представляет не частное от деления, а остаток.

Рассмотрим пример деления.

x 5 + x 3 + x

x 5 + x 3 + x 2

Остаток: R (x) = x 2 + x = 110

Формирование циклического кода.

Величина k показывает количество сдвигов влево, которое Q(x) должно претерпеть.

Пример: Q(x) = x 5 + x 3 + x = 101010 – исходная КК,

110 – контрольная часть

Остаток R(x) называется синдромом..

Пусть Q(x) = 1110. Если k =3, то Q(x) X k = 1110 000

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

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

Источник

Образующий полином циклического кода

Основы передачи дискретных сообщений

Тема 5. Защита от ошибок в системах связи

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

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

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

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

5.1 Понятие о корректирующих кодах

Пусть имеется источник сообщений с объемом алфавита К.

Если , то все последовательности (или кодовые комбинации) будут использоваться для кодирования сообщений, т.е. будут разрешенными.

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

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

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

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

Перебрав все возможные пары разрешенных комбинаций рассматриваемого кода можно найти минимальное расстояние Хемминга d₀.

Кодовое расстояние определяет способность кода обнаруживать и исправлять ошибки.

У простого кода d₀=1 – он не обнаруживает и не исправляет ошибки. Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В общем случае справедливы следующие соотношения

– для обнаруживающей способности

– для исправляющей способности

Двоичный блочный код является линейным если сумма по модулю 2 двух кодовых слов является также кодовым словом.

Линейные коды также называют групповыми.

Введем понятия группы.

Множество элементов с определенной на нем групповой операцией называется группой, если выполняется следующие условия:

Если выполняется условие g_i g_j = g_j g_i, то группа называется коммутативной.

Множество кодовых комбинаций n-элементного кода является замкнутой группой с заданной групповой операцией сложение по модулю 2.

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

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

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

5.2 ЦИКЛИЧЕСКИЕ КОДЫ

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

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

.

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

Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином.

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

Представление кодовой комбинации в виде многочлена.

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов).

В теории циклических кодов кодовые комбинации обычно представляются в виде полинома. Так, n-элементную кодовую комбинацию можно описать полиномом (n-1) степени, в виде

.

Запишем полиномы для конкретных 4-элементных комбинаций

Действия над многочленами.

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

,

поскольку .

Следует отметить, что действия над коэффициентами полинома (сложение и умножение) производятся по модулю 2.

Рассмотрим операцию деления на следующем примере:

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

Отметим, что запись кодовой комбинации в виде многочлена, не всегда определяет длину кодовой комбинации. Например, при n = 5, многочлену соответствует кодовая комбинация 00011.

Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

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

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

Формирование базиса (производящей матрицы) циклического кода

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

Полученная матрица и будет базисом циклического кода. Причем, в данном случае, разрешенные комбинации заведомо разделимы (т.е. информационные и проверочные элементы однозначно определены).

В данном случае код будет неразделимым.

Получив базис ЦК, можно получить все разрешенные комбинации, проводя сложение по модулю 2 кодовых комбинаций базиса в различных сочетаниях и плюс НУЛЕВАЯ.

Циклические коды достаточно просты в реализации, обладают высокой корректирующей способностью (способностью исправлять и обнаруживать ошибки) и поэтому рекомендованы МСЭ-Т для применения в аппаратуре ПД. Согласно рекомендации V.41 в системах ПД с ОС рекомендуется применять код с производящим полиномом

Построение кодера циклического кода

Рассмотрим код (9,5) образованный полиномом

.

Разрешенная комбинация циклического кода образуется из комбинации простого (исходного) кода путем умножения ее на и прибавления остатка R(x) от деления на образующий полином.

Пусть

тогда

Для реализации операции добавления нулей используется r-разрядный регистр задержки.

Как видим из примера, процедура деления одного двоичного числа на другое сводится к последовательному сложению по mod2 делителя [10011] с соответствующими членами делимого [10101], затем с двоичным числом, полученным в результате первого сложения, далее с результатом второго сложения и т.д., пока число членов результирующего двоичного числа не станет меньше числа членов делителя.

Это двоичное число и будет остатком .

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

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

Сформулируем правила построения ФПГ.

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

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

Структурная схема кодера циклического кода (9,5)

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

Рассмотрим работу этой схемы

1. На первом этапе К₁– замкнут К₂ – разомкнут. Идет одновременное заполнение регистров задержки и сдвига информ. элементами (старший вперед!) и через 4 такта старший разряд в ячейке №4

2. Во время пятого такта К₂ – замыкается а К₁ – размыкается с этого момента в ФПГ формируется остаток. Одновременно из РЗ на выход выталкивается задержание информационные разряды.

За 5 тактов (с 5 по 9 включительно) в линию уйдут все 5-информационных элемента. К этому времени в ФПГ сформируется остаток

3. К₂ – размыкается, К₁ – замыкается и в след за информационными в линию уйдут элементы проверочной группы.

4. Одновременно идет заполнение регистров новой комбинацией.

Второй вариант построения кодера ЦК.

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

Устройство деления на производящий полином можно реализовать в следующем виде:

За пять тактов в ячейках будет сформирован такой же остаток от деления, что и в рассмотренном выше Формирователе проверочной группы. (ФПГ).

За эти же 5 тактов информационные разряды, выданные сразу на модулятор.

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

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

Окончательно структурная схема экономичного кодера выглядит так.

— На первом такте Кл.1 и Кл.3 замкнуты, информационные элементы проходят на выход кодера и одновременно формируются проверочные элементы.

— После того, как в линию уйдет пятый информационный элемент, в устройстве деления сформируются проверочные;

— на шестом такте ключи 1 и 3 размыкаются (разрываются обратная связь), а ключ 2 замыкается и в линию уходят проверочные разряды.

Ячейки при этом заполняются нулями и схема возвращается в исходное состояние.

Определение ошибочного разряда в ЦК.

Пусть А(х)-многочлен соответствующий переданной кодовой комбинации.

Н(х)- многочлен соответствующей принятой кодовой комбинацией.

Тогда сложение данных многочленов по модулю два даст многочлен ошибки.

E(x)=A(x) H(x)

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

Остаток – полученный от деления принятого многочлена H(x) на производящей P_r(x) равен остатку полученному при делении соответствующего многочлена ошибок E(x) на P_r(x)

При этом ошибке в каждом разряде будет соответствовать свой остаток R(x) (он же синдром), а значит, получив синдром можно однозначно определить место ошибочного разряда.

Алгоритм определения ошибки.

Пусть имеем n-элементные комбинации (n = k + r) тогда:

1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде [1000000000], на образующей поленом P_r(x)

2. Делим полученный полином Н(х) на P_r(x) и получаем текущий остаток R(x).

3. Сравниваем R₀(x) и R(x).

— Если они равны, то ошибка произошла в старшем разряде.

— Если «нет», то увеличиваем степень принятого полинома на Х и снова проводим деления

в) Опять сравниваем полученный остаток с R₀(x)

— Если они равны, то ошибки во втором разряде.

— Если нет, то умножаем Н(х)х 2 и повторяем эти операции до тех пор, пока R(X) не будет равен R₀(x).

Ошибка будет в разряде соответствующем числу на которое повышена степень Н(х) плюс один.

Например: то номер ошибочного разряда 3+1=4

Пример декодирования комбинации ЦК.

Положим, получена комбинация H(х)=111011010

Проанализируем её в соответствии с вышеприведенным алгоритмом.

Реализуя алгоритм определения ошибок, определим остаток от деления вектора соответствующего ошибке в старшем разряде Х 8 на производяший полином P(x)=X 4 +X+1

X 8 +X 5 +X 4 x 4 +x+1

Разделим принятую комбинацию на образующий полином

Полученный на 9-м такте остаток, как видим, не равен R₀(X). Значит необходимо умножить принятую комбинацию на Х и повторить деление. Однако результаты деления с 5 по 9 такты включительно будут такими же, значит необходимо продолжить деление после девятого такта до тех пор, пока в остатке не будет R₀(Х). В нашем случае это произойдет на 10 такте, при повышении степени на 1. Значит ошибки во втором разряде.

Декодер циклического кода с исправлением ошибки

Если ошибка в первом разряде, то остаток R₀(X)=10101 появления после девятого такта в ячейках ФПГ.

На 10 такте старший разряд покидает регистр задержки и проходит через сумматор по модулю 2.

Если и этому моменту остаток в ФПГ=R₀(X), то логическая 1 с выхода дешифратора поступит на второй вход сумматора и старший разряд инвертируется.

В нашем случае инвертируется второй разряд на 11 такте.

5.3 Выбор образующего полинома

Рассмотрим вопрос выбора образующего полинома, который определяет корректирующие свойства циклического кода. В теории циклических кодов показано, что образующий полином представляет собой произведение так называемых минимальных многочленов m_i(x), являющихся простыми сомножителями (то есть делящимся без остатка лишь на себя и на 1) бинома x n + 1:

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

для любых значений l и t_и.ош существует циклический код длины n =2 l – 1, исправляющий все ошибки кратности t_и.ош и менее, и содержащий не более проверочных элементов.

Так как , то откуда . (**)

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

Таблица минимальных многочленов

Вид минимальных многочленов для

Определяя образующий полином, нужно из столбца для соответствующего соотношения выписать все многочлены, начиная с верхней строки до нижней с номером j=2t_и.ош–1 включительно. После этого следует перемножить выбранные минимальные многочлены в соответствии с (*). В частности, если r=3, t_и.ош=1, j=2*1-1=1, образующий полином будет представлять собой единственный минимальный многочлен P(x)= m₁(x) = x 3 +x+1 (первая строка, второй столбец таблицы ). Соответственно образующее число равно 1011.

Источник