Устройство перемежения/обратного перемежения для системы связи

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ПЕРЕМЕЖЕНИЯ / ОБРАТНОГО ПЕРЕМЕЖЕНИЯ ДЛЯ СИСТЕМЫ СВЯЗИ(71) Заявитель Учреждение образования Белорусский государственный технологический университет(72) Авторы Урбанович Павел Павлович Пацей Наталья Владимировна Шиман Дмитрий Васильевич Романенко Дмитрий Михайлович(73) Патентообладатель Учреждение образования Белорусский государственный технологический университет(57) Устройство перемежения / обратного перемежения, содержащее генератор адресов,первый и второй входы которого соединены с первым и вторым управляющими входами устройства соответственно, а выходы соединены с первыми адресными входами блока памяти, вторыми адресными входами соединенного с выходами счетчика, а информационными входами - с информационными входами устройства, информационные выходы которого соединены с выходами блока памяти, а входы синхронизации устройства соединены с третьим входом генератора адресов и входом счетчика, отличающееся тем, что содержит блок формирования дополнительных управляющих сигналов, первый и второй входы которого соединены с первым и вторым входами генератора адресов соответственно, а первый и второй выходы - с четвертым и пятым входами генератора адресов соответственно, выполненный с возможностью формирования и передачи на четвертый управляющий вход генератора адресов переменной 1, удовлетворяющей условию 11268 1 2008.10.30 1111,где 1(1-1)(1-1),1 и 1 - взаимно простые числа,111 - число строк,1 и 1 - простые числа,а также формирования и передачи на пятый управляющий вход генератора адресов переменной 2, удовлетворяющей условию 2221,где 2(2-1)(2-1),2 и 2 - взаимно простые числа,222 - число столбцов,2 и 2 - простые числа. Изобретение относится к системам связи и может быть использовано при создании устройств перемежения для формирования адреса в перемежителях с использованием единого алгоритма, а также в применяемых системах мобильной связи для повышения эффективности кода с исправлением ошибок в канале с замиранием и для повышения уровня защищенности информации от несанкционированного доступа. Известно техническое решение 1, реализующее обратный (реверсивный) способ перемежения/деперемежения. Известный способ основан на переупорядочивании битов кадра, изменяя их положение от старшего значения бита до младшего значения бита, в результате чего формируется чередующийся адрес (очередного символа выходной последовательности). Такой способ позволяет упростить алгоритм использования памяти, однако характеризуется неэффективным ее использованием при размере перемежителя не равном 2 ( - любое целое положительное число). Другое из известных устройств перемежения/обратного перемежения 2 состоит изпсевдошумовых генераторов, каждый из которых содержитустройств памяти, генератор адресов для добавления значения сдвига к размеру входных данных для обеспечения адреса, имеющего размер, кратный 2, и создание адресов, отличных от адресов, соответствующих значению сдвига. Это устройство создаетадресов, количество которых меньше 2 виртуальных адресов для считывания данных из памяти перемежителя, в котором запоминаютсябит данных. Устройство 2 обеспечивает необходимые значения кодового расстояния, весового параметра и характеристики рандомизации в системе связи. Недостатком устройства является высокая сложность, относительно низкое быстродействие. Наиболее близким техническим решением к предлагаемому изобретению является устройство перемежения/обратного перемежения 3, содержащее генератор адресов, первый, второй и третий входы которого соединены соответственно с первым, вторым и третьим управляющими входами устройства, а выходы генератора адресов соединены с первыми адресными входами блока памяти перемежителя, вторыми адресными входами соединенного с выходами счетчика, а информационными входами - с информационными входами устройства, информационные выходы которого соединены с выходами блока памяти перемежителя, а входы синхронизации устройства соединены с четвертым управляющим входом генератора адресов и входом счетчика. В этом устройстве, реализующем соответствующий способ перемежения/обратного перемежения, последовательно запоминаютсявходных битовых символов в блоке памяти перемежителя по адресу от 0 до -1, обеспечивают первую переменнуюи вторую переменную , удовлетворяющие соотношению 2 , и считывают -й (0-1) битовый символ по адресу, определяемому соотношением 2 (/), гдеявляется функцией для преобразования двоичного значения в десятичное путем ре 2 11268 1 2008.10.30 версирования битов. При этом первая переменнаяуказывает количество последовательных нулевых символов от младшего значения бита, когдапредставляется в двоичной форме. Вторая же переменнаяуказывает десятичное значение, соответствующее отброшенным битам, отличным от вышеуказанных последовательных нулевых бит. В известном устройстве 3 битовый символ считывают по адресу, определяемому отношением последовательностисчитывания к переменной(в двоичном виде), получаемой реверсированием битов двоичного значения с последующим преобразованием реверсированных бит в десятичное значение. С точки зрения технической реализации данный способ перемежения/обратного перемежения осуществляет перестановку бит входной последовательности, поступающей в блок памяти перемежителя через информационные входы с последующей записью в выходном буфере в виде новой (перемеженной) последовательности (блок памяти устройства перемежения состоит из буферов входных и выходных данных). Генератор адресов принимает по первому управляющему входу генератора адресов значение , равное размеру перемежителя, по второму, третьему и четвертому входам соответственно значения переменных ,(2 ) и синхроимпульсы (тактовые импульсы) для формирования адреса в памяти перемежителя (на выходах генератора) для считывания битовых символов, последовательно запоминаемых в блоке памяти перемежителя с его информационных входов. Блок памяти перемежителя последовательно запоминает входные битовые символы при работе в режиме записи и выводит на выходы блока битовые символы в соответствии с адресом на выходах генератора адресов в режиме считывания. Счетчик считает входные тактовые импульсы и формирует на своих выходах адрес записи. Таким образом, известное решение 3 позволяет сравнительно эффективно осуществлять перемежение (перестановку) символов исходной (входной) последовательности избит, обеспечивая возможность разнесения группирующихся (расположенных в соседних разрядах) ошибок на некоторое расстояние. Известный способ и устройство перемежения/обратного перемежения характеризуется постоянной глубиной перемежения (минимальное расстояние, на которое разносятся два соседних символа), что позволяет легко исправить группирующиеся ошибки (пакет) соответствующей кратности. Однако известно, что кратность ошибки может быть различной. Причем, при передаче данных достаточно большой длительности и объема (минуты и более мегабайты и более) могут встречаться пакеты ошибок разной длины. Вместе с тем,вероятность появления ошибки меньшей кратности является тоже высокой 4. Известное устройство характеризуется сравнительно низкой глубиной перемежения символов, не удовлетворяющей практическим потребностям. Задачей изобретения является повышение глубины перемежения символов, что должно обеспечить, в свою очередь, возможность исправления ошибок большей кратности в информационной последовательности. Поставленная задача решается тем, что в устройство перемежения/обратного перемежения, содержащее генератор адресов, первый и второй входы которого соединены соответственно с первым и вторым управляющими входами устройства, а выходы генератора адресов соединены с первыми адресными входами блока памяти перемежителя, вторыми адресными входами соединенного с выходами счетчика, а информационными входами - с информационными входами устройства, информационные выходы которого соединены с выходами блока памяти перемежителя, а входы синхронизации устройства соединены с третьим входом генератора адресов и входом счетчика, отличающееся тем, что содержит блок формирования дополнительных управляющих сигналов, первый и второй входы которого соединены соответственно с первым и вторым входами генератора адресов, а первый и второй выходы блока - с четвертым и пятым входами генератора адресов,отличающееся тем, что на четвертом управляющем входе генератора адресов формирует 3 11268 1 2008.10.30 ся переменная , удовлетворяющая условию 1111, где 1(1-1)(1-1), 1 и 1 - взаимно простые числа, 111,1 и 1 - простые числа, кроме того, на пятом управляющем входе генератора адресов формируется переменная 2, удовлетворяющая условию 2221, где 2(2-1)(2-1), р 2 и 2 - взаимно простые числа,222, а е 2 и 2 - простые числа. Сущность предлагаемого технического решения основана на использовании матрицы,строки и столбцы которой формируются последовательностью входных символов, образующих пакет данных. Для удобной работы каждый символ помечается (индексируется),пакеты данных индексируются как множества строк и столбцов, ограниченных в размере. Произведение заранее установленных размеров строк (1) и столбцов (2) соответствует объему блока данных (12). Перемежение данных базируется на алгоритме разбрасывания данных за счет обработки бит по частям. Блок перемежения содержит память, предназначенную для обработки и хранения пакетов данных. Он построен и функционирует по тому же принципу, что и блок перемежения известного устройства 3. Изобретение поясняется чертежами фиг. 1 - схема устройства перемежения/обратного перемежения,фиг. 2 - схема перестановки строк и столбцов,фиг. 3 - сравнительная характеристика минимального разнесения бит для размера перемежителя 196, где 1 - характеристика для устройства 3, 2 - для предлагаемого решения при 114, 13, 214, 23,фиг. 4 - сравнительная характеристика минимального разнесения бит для размера перемежителя 700, где 1 - характеристика для устройства 3, 2 - для предлагаемого решения при 150, 111, 214, 23, 3 - для предлагаемого решения при 150,13, 214, 23, 4 - для предлагаемого решения при 114, 13, 250, 23, 5 для предлагаемого решения при 114, 13, 250, 211. Процессор (на фигуре не показан) связан с памятью и используется для разделения пакетов данных на части. Он также предназначен для генерации перемешивания последовательного множества частей данных и индексации множества строк и столбцов. Схематично принцип перестановки строк и столбцов матрицы данных показан на фиг. 2. Для примера в табл. 1 показано первоначальное расположение данных (входные биты) в матрице размером 1414 (196, 114, 214). Таблица 1 Исходная матрица 1414 11268 1 2008.10.30 Предлагаемый способ перемежения символов (строк и столбцов) основывается на использовании простых чисел. Для начала выбираются взаимно простые числа р 1 и 1 такие, что 111. Вычисляется 1(1-1)(1-1). Находятся два простых числа (1 и 1) таких, чтобы 1111. Количество строкопределяется как -1. В табл. 2 представлены возможные варианты сочетания числа строк 1 и столбцов 2, а также соответствующие этим сочетаниям значения , , , ,(в общем случае каждая из переменных может быть обозначена любым из вышеизложенных индексов - 1, 2). Таблица 2 Параметры перемежителя для различных 1 и 2 3 5 15 14 2 4 8 3 3 3 11 33 32 2 10 20 3 7 3 13 39 38 2 12 24 5 5 3 17 51 50 2 16 32 3 11 3 29 87 86 2 28 56 3 19 5 7 35 34 4 6 24 5 5 5 13 65 64 4 12 48 7 7 5 17 85 84 4 16 64 5 13 5 31 155 154 4 30 120 11 11 7 23 161 160 6 22 132 7 19 7 29 203 202 6 28 168 13 13 11 13 143 142 10 12 120 11 11 11 17 187 186 10 16 160 7 23 11 23 253 252 10 22 220 13 17 11 31 341 340 10 30 300 7 43 13 19 247 246 12 18 216 7 31 13 31 403 402 12 30 360 19 19 17 19 323 322 16 18 288 17 17 17 31 527 526 16 30 480 13 37 19 29 551 550 18 28 504 5 101 29 31 899 898 28 30 840 29 29 Перемежение множества строк(1) осуществляется на основе формулы(1)11. Данная формальная запись означает, что -я строка исходной матрицы переместится на-ю позицию после перемежения. При 114, 214, например, 13 и 15. Тогда 3515, 1248. Выбираем е 13 и 13 для выполнения условия 3381. Тогда, для примера, определим место расположения строк после выполнения процедуры перемежения 113151 (1,1),223158 (2,8),3331512 (3,12),443154 (4,4),553155 (5,5),663156 (6,6),7731513 (7,13),883152 (8,2),993159 (9,9),101031510 (10,10),111131511 (11,11),5 11268 1 2008.10.30 12123153 (12,3),13133157 (13,7),141431514 (14,14). Результаты первого этапа перемежения (строк) входной последовательности представлены в табл. 3. Таблица 3 Матрица 1414 после перемежения строк 1 2 3 4 5 6 7 8 9 10 11 12 13 14 99 100 101 102 103 104 105 106 107 108 109 110 111 112 155 156 157 158 159 160 161 162 163 164 165 166 167 168 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 169 170 171 172 173 174 175 176 177 178 179 180 181 182 15 16 17 18 19 20 21 22 23 24 25 26 27 28 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 29 30 31 32 33 34 35 36 37 38 39 40 41 42 85 86 87 88 89 90 91 92 93 94 95 96 97 98 183 184 185 186 187 188 189 190 191 192 193 194 195 196 Второй этап перемежения связан с обработкой столбцов. Новое местоположение столбца(1 ус) определяется согласно формальной записи(2)22,где 2 - произведение взаимно простых чисел р 2 и 2. Причем 2(2-1)(2-1). Числа 2 и е 2 выбирают так, чтобы выполнялось условие 2221. Количество столбцов 2 определяется как -1. Формальная запись (2) означает, что -й столбец исходной матрицы переместится на -ю позицию после перемежения. Определим место расположения столбцов после выполнения процедуры перемежения 113151 (1,1),223158 (2,8),3331512 (3,12),443154 (4,4),553155 (5,5),663156 (6,6),7731513 (7,13),883152 (8,2),993159 (9,9),101031510 (10,10),111131511 (11,11),12123153 (12,3),13133157 (13,7),141431514 (14,14). После перемежения строк и столбцов местоположение данных меняется. Итоговый результат отображен в табл. 4. Матрица 1414 после перемежения строк и столбцов Последовательность выходных битовых символов перемежителя получается 1, 99, 155,43, 57, 71, 169, 15, 113, 127, 141, 29, 85, 183, 8, 106, 162, 50, 64, 78, 176, 22, 120, 134, 148,36, 92, 190, 12, 11042, 98, 196. Для определения минимального кодового расстояния необходимо найти наименьшую разность из двух соседних чисел (количество строк, количество столбцов). В данном примере это число 14. Отметим, что в известном решении 3 выходная последовательность 196 битовых символов имеет вид 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85,89, 93, 97, 101, 105, 109, 113, 117, 121, 125, 129, 133, 137, 141, 145, 149, 153, 157, 161, 165,169, 173, 177, 181, 185, 189, 193, 3, 7, 11, 15,188, 192, 196, и характеризуется минимальным кодовым расстоянием, равным 4. Сравнительная характеристика минимального разнесения бит для блока перемежения размером в 196 бит отображена на фиг. 2, где 1 характеристики для известного решения 3, 2 - характеристики для предлагаемого решения при 114, 13, 214, 23. На фиг. 1 показана схема устройства перемежения/обратного перемежения. Устройство содержит первый 1 и второй 2 управляющие входы, блок 3 формирования дополнительных управляющих сигналов, которые вычисляют значения 1 и 2, исходя из значений размера матрицы 1 и 2. Сформированные степенные коэффициенты 1 и 2 из блока 3 поступают на четвертый 4 и пятый 5 выходы генератора адресов 7. Генератор адресов 7 принимает значения размера матрицы (по входам 1 и 2), степенных коэффициентов (по входам 4 и 5) и тактовые импульсы 6. В результате работы генератора адресов 7 на выход 8 подается значение адреса считывания, поступающего на первые адресные входы блока памяти 12. Счетчик 9 считает входные тактовые импульсы 6 и выдает значение счетчика тактовых импульсов на вторые адресные входы 10 блока 12 в виде значения адреса записи. Память перемежителя 12 последовательно запоминает входные битовые символы 11 при работе в режиме записи и выводит битовые символы в соответствии с адресом 8, обеспечиваемым генератором 7 адресов, при работе в режиме считывания. После перемежения, биты матрицы из памяти перемежителя 12 передаются на информационные выходы 13 устройства. Генератор адресов 7 формирует адрес считывания 8 в соответствии с формулой 11268 1 2008.10.30 где- адрес памяти (0( - 1,- целочисленное деление в приведенном соотношении учитывается тот факт, что считывание символов (на выход устройства) осуществляется по столбцам. Данная формальная запись означает, что -й символ двукратно перемеженной (по строкам и столбцам) последовательности будет считан на выход под -м номером . Для примера приведем расчет -х адресов выходной матрицы 1414 (0195) с учетом изменения порядка адресов начиная с нулевого адреса (ему соответствует индекс 1 входной последовательности) 0 0)1)315)1195 (151)1)315)1)(151)195 . 195 151 Обратное перемежение также осуществляется по схеме, приведенной на фиг. 1, за исключением того, что в блоке 3 на его выходы 4 и 5 подаются значения 1 и 2. Генератор адресов 7 формирует адрес считывания 8 в соответствии с формулой)1)11)1( 21)1)22)1)(11), (4) 2 1 где считывание также осуществляется по столбцам. Анализ разнесения ошибок при различных размерах блока перемежения показал увеличение минимального расстояния по сравнению с устройством 3. Например, при 196 бит (фиг. 3, 14, 13, 214, 23) расстояние между битами тройной ошибки для предлагаемого решения равно 14, для устройства 3 равно 4, а при 700 бит (фиг. 4, 5 график для предлагаемого решения при 114, 13, 250, 211) соответствующие показатели равны 50 и 4 соответственно. Таким образом, предлагаемое устройство выполняет те же функции, что и известное осуществляет перемежение символов в режиме передачи данных в канале связи и обратное перемежение (деперемежение) - в режиме обработки данных на выходе канала связи. Однако предлагаемое решение позволяет значительно повысить расстояние между разнесенными символами (от нескольких раз до десятков раз), что, в свою очередь, обеспечивает повышение уровня надежности передачи данных за счет коррекции группирующихся ошибок наиболее вероятной кратности (до 68). Перечень предприятий, на которых может быть использовано изобретение операторы сотовой связи (например, ), Интернет-провайдеры (например Белтелеком, ,). Источники информации 1. Патент КНР 19980054131, МПК Н 03 М 13/27, 1998. 2. Патент РФ 2210186, МПК Н 03 М 13/27, 2003. 3. Патент РФ 2216099, МПК Н 03 М 13/27, 2000 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 9