621.3.085
Применение кодов Хемминга в цифровых преобразователях угла на основе псевдослучайных кодовых шкал
А. А. ОЖИГАНОВ
Национальный исследовательский университет информационных технологий, механики
и оптики, С.-Петербург, Россия, e-mail: ojiganov@mail.ifmo.ru
Показано применение кодов Хемминга с возможностью исправления одиночных ошибок считывания в цифровых преобразователях угла, выполненных на основе псевдослучайных кодовых шкал. Приведены пример расчета и функциональная схема преобразователя.
Кпючевые слова: преобразователь угла, псевдослучайная кодовая шкала, считывающие элементы, код Хемминга.
The application of Hamming codes with possibility of single reading errors correction in digital angle converters based on the pseudo-random code scales is shown. An example of calculation and the converter functional diagram are presented.
Key words: angle converter, pseudo-random codes scale, reader elements, Hamming code.
В цифровых преобразователях угла (ЦПУ), построенных по методу считывания, широко применяют классические (двоичные, двоично-сдвинутые, двоично-десятичные, циклические и функциональные) кодовые шкалы (КШ). Основным недостатком таких шкал является сложность изготовления кодированного элемента, так как каждому разряду шкалы обычно соответствует отдельная дорожка [1]. Повысить информационную надежность ЦПУ на основе классических КШ можно при использовании в них корректирующих кодов, что приведет к значительному увеличению массогабаритных показателей как самих шкал, так и преобразователей в целом. Следовательно, необходимо использовать в КШ дополнительные контрольные кодовые дорожки.
В настоящей статье рассмотрена возможность повышения информационной надежности ЦПУ без использования в КШ дополнительных контрольных кодовых дорожек. Показано практическое применение кодов Хемминга в ЦПУ, выполненных на основе разработанных КШ, приведен пример расчета и функциональная схема преобразователя.
В работах [2—5] рассмотрены псевдослучайные КШ, которые более технологичны в изготовлении по сравнению с классическими и имеют меньшие габаритные размеры. У таких шкал одна информационная дорожка, выполненная в соответствии с символами псевдослучайной двоичной последовательности максимальной длины (М-последователь-ности) {а} = а0, а1,..., аМ-1, и п считывающих элементов (СЭ), размещенных вдоль дорожки. При полном обороте шкалы со СЭ можно получить М = 2п-1 различных п разрядных кодовых комбинаций и обеспечить разрешающую способность ЦПУ 8 = 3607М.
Формирование кодов с возможностью исправления и (или) обнаружения ошибок считывания возможно в псевдослучайных КШ при введении в них избыточности по числу СЭ без использования дополнительных контрольных кодовых дорожек. Общие принципы формирования корректирующих кодов с таких шкал сформулированы в [3, 4, 6, 7].
Рассмотрим предпосылки, касающиеся построения псевдослучайных КШ на основе М-последовательностей и при-
менения в таких шкалах кодов Хемминга с минимальным кодовым расстоянием 6=3.
Для генерации М-последовательности с длиной периода
п
М = 2п-1 используют примитивный полином Ь(х) = £ Л,х',
I =0
где Ь0 = Ьп = 1, а = 0,1 при 0 < / < п.
Символы М-последовательности ап+у удовлетворяют ре-
п-1
куррентному выражению ап+у = 5 а/+у Л/, у = 0, 1,..., где знак Е
/=0
означает суммирование по модулю два, а индексы при символах берутся по модулю М. Начальные значения а0, а1,..., ап-1 можно выбирать произвольно, за исключением нулевой комбинации. Для определенности при построении круговой псевдослучайной КШ символы а0, а1,..., ам-1 отображаются на информационной дорожке по ходу часовой стрелки.
М-последовательности относятся к классу циклических кодов, и их можно задавать с помощью порождающего полинома д(х) = (хМ+1)/Л(х). Для каждой М-последовательнос-ти с длиной периода М существует ровно М различных циклических сдвигов, полученных при умножении порождающего полинома д(х) на ху, где у = 0, 1, ..., М - 1.
Так как псевдослучайные КШ строятся в соответствии с символами М-последовательсти, то путем циклических сдвигов можно определить порядок размещения на шкале п СЭ, т. е. элементу т, т = 1, 2, ..., п ставится в соответствие циклический сдвигут х 1тд(х) М-последовательности. Тогда полином, определяющий порядок размещения на шкале п СЭ, п
имеет вид г(х) = £х1т, гдеут е {0, 1, ..., М-1}.
т=1
Приняв в выражении для г(х) у1 = 0, получим положения 2-го, 3-го,..., п-го СЭ, смещенные относительно первого элемента нау2,у3, ...,уп элементарных участков (квантов) информационной дорожки шкалы, соответственно.
В табл. 1 приведены полиномы Л(х) до п=12 включительно, которые могут быть использованы для генерации соответствующих М-последовательностей.
Т а б л и ц а 1
Примитивные полиномы
Поясним вариант построения псевдослучайных КШ. Примем для простоты п=4 и выберем из табл. 1 полином Ь(х) = = х4+х+1, где = Ь1=Ь4=1,..., ^2=^3=0. Здесь длина периода последовательности М=24—1 =15, а М-последовательность {а} = а0а1а2аэа4а5а6а7а8ада10а11 а12а13а14 = 000100110101111. При начальных значениях М-последовательности а0=а1=а1=0, а3=1; остальные ее символы получены в соответствии с рекуррентным выражением, которое в данном примере имеет вид а4+. = а1+! Фа.,} = 0, 1,...,10. Размещение четырех считывающих элементов СЭ1, СЭ2, СЭ3, СЭ4 вдоль кодовой дорожки шкалы задано полиномом г(х) = 1+х+х2+х3.
При построении информационной дорожки М-последо-вательность с длиной периода М=1 5 должна быть нанесена на шкалу в виде активных (единицы) и пассивных (нули) ее участков, например по ходу часовой стрелки, причем на информационную дорожку наносится только один период этой последовательности. М-последовательность с длиной периода М=2п-1 определяет число квантов информационной дорожки кодового диска, равное в данном примере 15. Тогда значение кванта 8=3607М=360°/15=24°. Считывающие элементы числом п должны быть размещены на информационной дорожке шкалы согласно г(х) с шагом, равным одному кванту шкалы 8, например по ходу часовой стрелки. На рисунке приведена линейная развертка четырехразрядной псевдослучайной КШ.
Последовательно фиксируя СЭ1, СЭ2, СЭ3, СЭ4 кодовую комбинацию при перемещении шкалы на один квант против хода часовой стрелки, получаем 15 различных 4-разрядных кодовых комбинаций. Эти комбинации приведены в табл. 2.
Т а б л и ц а 2
Кодовые комбинации четырехразрядной псевдослучайной КШ
В начале 1950-х гг. Хеммингом был предложен код с обнаружением и исправлением одиночной ошибки (минимальное кодовое расстояние й=3) [8]. Для синтеза такого кода необходимо решить следующие задачи:
определить число контрольных символов (К), обеспечивающих заданные требования по помехозащищенности; установить, на каких позициях кодовой комбинации следует разместить контрольные символы и какие позиции займут информационные (И); определить значение каждого контрольного символа, собрав макет кодовой комбинации; составить кодовые комбинации, включающие как контрольные, так и информационные символы; привести алгоритм проверок, позволяющий установить существование и место ошибки.
Рассмотрим синтез кода Хемминга с й=3 применительно к данной задаче. Количество дополнительных СЭ (ДСЭ) к равно числу контрольных символов в коде Хемминга и определяется из соотношения к = ]1од2{(п+1)+] 1од2(п+1)[}[, где п — число СЭ, равное количеству информационных символов в коде Хемминга, а знак ]...[ означает округление до ближайшего большего целого.
Рассчитаем число ДСЭ к. Для п=4...12 к=3, 4, 4, 4, 4, 4, 4, 4, 5.
Определим места, на которых в общей кодовой комбинации располагаются контрольные разряды. Контрольные символы должны составить двоичное число (синдром ошибки), которое бы указывало номер ошибочной позиции. В результате первой проверки на четность получается символ первого (младшего) разряда синдрома, в результате второй проверки — символ второго и т. д. Таким образом, если синдром ошибки представить в виде двоичного числа, а рядом записать соответствующие десятичные эквиваленты, то получим табл. 3.
Далее последовательно выпишем номера позиций, участвующих в каждой проверке на четность. В п ерво й п роверке должны фигурировать те позиции, которые содержат единицу в младшем разряде. Таким образом, это будут 1, 3, 5, 7, 9, 11, 13, 15, 17. Во второй проверке — позиции, содержащие единицу во втором разряде, т. е. 2, 3, 6, 7, 10, 11, 14, 15. В третьей проверке должны участвовать 4, 5, 6, 7, 12, 13, 14, 15 позиции, в четвертой — 8, 9, 10, 11, 12, 13, 14, 15, а в пятой — 16, 17. Полученные результаты приведены в табл. 4.
№ положения псевдослучайной КШ СЭ1 СЭ2 СЭ3 СЭ4 Десятичный эквивалент кода
0 0 0 0 1 1
1 0 0 1 0 2
2 0 1 0 0 4
3 1 0 0 1 9
4 0 0 1 1 3
5 0 1 1 0 6
6 1 1 0 1 13
7 1 0 1 0 10
8 0 1 0 1 5
9 1 0 1 1 11
10 0 1 1 1 7
11 1 1 1 1 15
12 1 1 1 0 14
13 1 1 0 0 12
14 1 0 0 0 8
п т М = 2п-1 п Ь(х) М = 2п-1
1 х+1 1 7 х7+х+1 127
2 х2+х+1 3 8 х8+х6+х5+х+1 255
3 х3+х+1 7 9 х9+х4+1 511
4 х4+х+1 15 10 х10+х3+1 1023
5 х5+х2+1 31 11 х11+х2+1 2047
6 х6+х+1 63 12 х12+х7+х4+х3+1 4095
Т а б л и ц а 3 Синдром ошибки
Синдром ошибки Десятичный эквивалент
00001 1
00010 2
00011 3
00100 4
00101 5
00110 6
00111 7
01000 8
01001 9
01010 10
01011 11
01100 12
01101 13
01110 14
01111 15
10000 16
10001 17
Т а б л и ц а 4
Номера проверок и позиций
№ проверки Позиции, охватываемые проверкой
Первая 1 3 5 7 9 11 13 15 17
Вторая 2 3 6 7 10 11 14 15 —
Третья 4 5 6 7 12 13 14 15 —
Четвертая 8 9 10 11 12 13 14 15 —
Пятая 16 17
Из табл. 4 следует, что контрольные символы Кт должны размещаться на следующих позициях: К1 на позиции 1, т. е. 20; К2 на 2, т. е. 21; К3 — на 4, т. е. 22; К4 — на 8, т. е. 23; К5 — на 16, т. е. 24. Позиции 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17 должны занять соответственно информационные символы И11, И10, Ид, И8, И7, И6, И5, И4, И3, И2, И1, И0.
В рассматриваемой задаче этот результат необходимо применять следующим образом. С первого СЭ должны формироваться символы И0, со второго — И1, ... , с двенадцатого — И11, а с первого ДСЭ — символы К1, со
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.