Быстрый псевдослучайный перемежитель

Изобретение относится к области радиотехники и может быть использовано в составе цифровых передатчиков и приемников. Техническим результатом является уменьшение задержки и упрощение реализации устройства. Устройство содержит область памяти, организованную в виде двух идентичных K-разрядных регистров сдвига с параллельным выводом информации и с тремя состояниями выхода, соответствующие выходы регистров объединены между собой в K общих выводов, которые в псевдослучайном порядке, согласно перестановке выводов, подключены к информационным входам мультиплексора. Устройство также содержит суммирующий счетчик с модулем пересчета K, считающий на частоте поступления входных битов, триггер, работающий в счетном режиме, два логических элемента «И». 6 ил.

 

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

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

Функционирование традиционного блочного перемежителя описано в [1] на стр. 486-488.

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

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

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

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

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

Так, наиболее близким к заявляемому изобретению по технической сущности и достигаемому результату является псевдослучайный перемежитель, устройство которого описано в [4] на стр. 327-330 и на рис. 8.11 (стр. 328) показана его структурная схема.

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

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

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

Технический результат от использования изобретения заключается в уменьшении задержки псевдослучайного перемежителя и упрощении его реализации на программируемой логической интегральной схеме (ПЛИС).

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

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

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

1. Вместо ЗУПВ используются регистры сдвига с параллельным выводом информации.

2. Вместо хранения псевдослучайной перестановки в адресном ПЗУ используется псевдослучайный порядок подключения выходов регистров сдвига к информационным входам мультиплексора.

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

Благодаря новой совокупности существенных признаков, технический результат – уменьшение задержки псевдослучайного перемежителя и упрощение его реализации на ПЛИС, достигается за счет:

1. Отсутствия ПЗУ, а значит и времени считывания из ПЗУ.

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

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

Проведенный анализ уровня существующей техники позволил установить, что аналоги, характеризующиеся совокупностью признаков тождественных всем признакам заявленного технического решения, отсутствуют. Это указывает на соответствие заявленного устройства условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Функциональная схема предлагаемого устройства представлена на фиг. 1. Быстрый псевдослучайный перемежитель содержит область памяти, организованную в виде двух идентичных K-разрядных регистров сдвига 5, 6 с параллельным выводом информации и с тремя состояниями выхода, при этом соответствующие выходы данных регистров объединены между собой в K общих выводов 7; где DS (Data Serial) – последовательный вход данных; С (Clock) – тактовый вход; EO (Enable Output) – вход разрешения выхода, то есть наличие логической единицы («лог. 1») на входе EO переводит выходы DO (Data Output) регистра в высокоомное третье состояние. Выводы 7 в псевдослучайном порядке, согласно перестановке выводов 8, подключены к информационным входам DI (Data Input) мультиплексора 9, адресные входы A (Address) которого подключены к выходам суммирующего счетчика 1 с модулем пересчета K (то есть по mod K), считающего на частоте поступления входных битов, причем последний n-ый выход счетчика 1 подключен к входу триггера 2, работающего в счетном режиме, прямой выход триггера 2 подключен к входу EO регистра сдвига 5 и к нижнему входу двухвходового логического элемента (ЛЭ) «И» 3, а инверсный выход триггера 2 подключен к входу EO регистра сдвига 6 и к нижнему входу ЛЭ «И» 4, при этом верхние входы ЛЭ «И» 3 и ЛЭ «И» 4 предназначены для тактовых импульсов. Регистры сдвига, мультиплексор, счетчик, триггер могут быть выполнены любым общеизвестным способом. Вместо триггера можно использовать последний выход счетчика по mod 2K.

Псевдослучайный перемежитель работает следующим образом. Поступающие на вход псевдослучайного перемежителя биты данных подаются на входы DS регистров сдвига 5, 6. Синхронно с битами данных на вход счетчика 1 и верхние входы ЛЭ «И» 3, 4 поступают тактовые импульсы. На прямом выходе триггера 2 логический ноль (лог. «0»), тогда на входе EO регистра сдвига 5 лог. «0», а на входе EO регистра сдвига 6 лог. «1», то есть регистр сдвига 5 находится в режиме чтения, регистр сдвига 6 находится в режиме записи и тактовые импульсы не поступают на вход C регистра сдвига 5 (лог. «0» на нижнем входе ЛЭ «И» 3) и поступают на вход C регистра сдвига 6 (лог. «1» на нижнем входе ЛЭ «И» 4). С приходом нового тактового импульса очередной бит данных записывается в регистр сдвига 6, а данные, записанные в регистр сдвига 6 ранее, сдвигаются на один разряд вправо. Выходы DO регистра сдвига 6 отключены (находятся в третьем состоянии) от общих выводов 7, в то же время выходы DO регистра сдвига 5 в псевдослучайном порядке, согласно перестановке выводов 8, подключены к информационным входам DI мультиплексора 9. Счетчик 1 в i-ый момент времени генерирует на адресных входах A мультиплексора 9 значение . При этом мультиплексор 9 переводит бит данных с -ого выхода DO регистра 5 на свой выход DO (выход устройства). Через каждые K тактовых импульсов триггер 2 меняет выходное состояние и переключает режим работы соответствующего регистра на противоположный, то есть регистр сдвига 5 и регистр сдвига 6 меняются ролями.

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

Для псевдослучайного перемежителя можно использовать любую перестановку. Например, в турбоподобных кодах, отличными характеристиками обладает S-случайная перестановка [5], а также ее модификации [6, 7] и комбинации [8].

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

если , то ,

Так, при , , возможна следующая перестановка:

.

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

Для генерирования перестановки S-случайного перемежителя можно воспользоваться алгоритмом, блок-схема которого представлена в [9]. Данный алгоритм в среде MATLAB выглядит следующим образом.

% Исходными данными являются значения K и S

p=randperm(K); % вектор p – случайная перестановка

for i=1:K

for l=1:length(p)

pp(i)=p(l); % вектор pp – S-случайная перестановка

for j=1:S

quit=(i-j<=0);

if quit

break;

end;

quit1=(abs(pp(i)-pp(i-j))<=S);

if quit1

break;

end;

end;

if quit

break;

end;

if quit1

else break;

end;

end;

p(l)=[];

end;

S-случайная перестановка обладает важными свойствами:

– свойство расстояния, которое означает, что между близлежащими элементами исходного блока, поддерживается определенное расстояние в перемеженном блоке;

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

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

– сократимость (prunability), которое означает, что перестановка должна обеспечивать определенные расстояния и степени случайности для перестановок меньших размеров, полученных на основе исходной;

– бесконфликтность (contention free), которое связано с широким распространением параллельных вычислений и означает, что не происходит обращения к одним и тем же ячейкам памяти перемежителя одновременно, бесконфликтность достигается специальным подбором позиций в перестановке.

Имеется много работ, в которых представлены перестановки, удовлетворяющие перечисленным свойствам, например [6-8].

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

Исследование предлагаемого устройства проведено на персональной ЭВМ посредством имитационного моделирования в среде Multisim. Проведенное исследование подтвердило заявленный технический результат.

Вариант осуществления (на S=1 S-случайной перестановке ) быстрого псевдослучайного перемежителя, соответствующего изобретению, рассмотрен в электронной системе моделирования Multisim 14 и поясняется иллюстрациями на которых представлены:

фиг. 3 – вид предлагаемого устройства в рабочем окне Multisim 14 согласно варианту осуществления настоящего изобретения;

фиг. 4 – вид подсхемы для регистра сдвига D5 (D6) из фиг. 3;

фиг. 5 – вид перестановки выводов Permutation из фиг. 3;

фиг. 6 – временные диаграммы начального этапа работы предлагаемого устройства в окне Multisim 14 согласно варианту осуществления настоящего изобретения.

Литература

1. Скляр Б. Цифровая связь. Теоретические основы и практическое применение, 2-е изд. / Б. Скляр ; Пер. с англ. Е.Г. Грозы [и др.]; под редакцией А.В. Назаренко – М. : Вильямс, 2003. – 1104 с.

2. Corrado-Bravo C.J., Rubio I. Algebraic construction of interleavers using permutation monomials, IEEE Communication Society. 2 (2004), pp. 911-915.

3. Патент РФ 2235424 кл. H03M 13/27 опубл. 27.08.2004. Перемежитель турбокода, использующий линейные конгруэнтные последовательности / Линг Ф., Ровитч Д.Н.

4. Кларк Дж., мл. Кодирование с исправлением ошибок в системах цифровой связи / Дж. Кларк, мл., Дж. Кейн ; Пер. с англ. C.И. Гельфанда; под редакцией Б.С. Цыбакова – М. : Радио и связь, 1987. – 392 с.

5. Dolinar S., Divsalar D. Weight distributions for turbo codes using random and nonrandom permutations. 1995. TDA Progress Report 42-122, Jet Propulsion Laboratory, Pasadena, California, pp. 56-65.

6. Popovski P., Kocarev L., Risreski A. Design of flexible-length S-random interleaver for turbo codes, IEEE Commun. Letter, 2004, Vol. 8, No. 7, pp. 461-463.

7. Dinoi L., Bendetto S. Design of fast prunable S-random interleavers. IEEE Trans. Wireless Commun., 2005, Vol. 4, No. 5, pp. 1-9.

8. Gazi O. Prunable collision free random interleaver design. Wireless Personal Communications, 2012, Vol. 65, pp. 555-566.

DOI 10.1007/s11277-011-0272-0

9. Баринов А.Ю. Перемежение в канальном кодировании: свойства, структура, специфика применения. Журнал радиоэлектроники [электронный журнал]. 2019. №1. Режим доступа: http://jre.cplire.ru/jre/jan19/13/text.pdf

DOI 10.30898/1684-1719.2019.1.13

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