COMMUNICATION SYSTEMS WITH TIME DIVISION MULTIPLE ACCESS
OF CHANNELS BASED ON HERST'S INDICATOR
Kletskov D.A., candidate of technical sciences
Permyakov A.S.
Cherepovets highest military engineering college of radio electronics
Russian Federation 162600 Vologda Region, Cherepovets, Sovetsky Ave., 126
Abstract. The article proposes a method for recognizing service packets of the control channel of satellite communication systems that use time division multiple access for servicing subscribers based on estimating their self-similarity. The method is based on the evaluation of Hurst's indicator of service packets of the control channel and information packets with different type of subscriber load. The evaluation of the Hurst's indicator is carried out by means of the analysis of time series composed of the difference of the time instants between packets of the corresponding type, using an approved R/S analysis technique.
Keywords: self-similarity, Hurst's indicator, time series, normalized range, R/S analysis.
УДК 621.391:519.72
ГРНТИ 49.03.03
Подход к временному уплотнению и перемежению двоичных
Последовательностей на основе математических операций
Перестановки бит
Печурин М.В., кандидат технических наук,
Мусатов Е.А.,
Гуков М.С.
Череповецкое высшее военное инженерное училище радиоэлектроники
Российская Федерация, 162622, Вологодская обл., г. Череповец, Советский пр., 126
Аннотация. Рассмотрена возможность применения математических операций перестановки бит при формировании сигналов систем цифровой связи. Проведен анализ результативности использования таких операций на этапах временного уплотнения и перемежения двоичных последовательностей. Показано, что наибольшей результативности позволяет достичь операция реверса бит.
Ключевые слова: временное уплотнение, перемежение, перестановка бит.
| С |
овременные системы цифровой связи включают несколько этапов преобразований сигналов, в том числе временное уплотнение (ВУ) и перемежение двоичных последовательностей (ДП). Задачей ВУ является оптимизация использования ресурса коллективного канала связи. Перемежение же предназначено для рассредоточения пакетов ошибок, что, в свою очередь, позволяет применять более простые помехоустойчивые коды на этапе канального кодирования [2].
Традиционные подходы к ВУ и перемежению ДП обладают рядом недостатков. Так, в первом случае информация абонентов объединяется последовательно, вследствие чего время ожидания каждого абонента занимает большую часть цикла ВУ, а буферная память устройств мультиплексирования используется не рационально [3]. Во втором же случае требуется адаптация параметров перемежения к характеристикам каналов связи и канальных кодеров [1].
Уменьшить влияние указанных недостатков позволяет: на этапе ВУ – равномерное распределение информации каждого абонента в пределах цикла ВУ; на этапе перемежения – использование алгоритмов, которые рассредоточивают рядом расположенные символы обратно пропорционально расстоянию между ними по некоторому почти случайному закону.
Сформулируем два утверждения для анализа и описания процессов ВУ и перемежения ДП.
Утверждение 1. ДП с ВУ есть упорядоченное множество канальных интервалов { s } LF, где под канальным интервалом s понимается временной интервал, занимающий определенное положение в цикле ВУ и выделяемый для отдельного абонентского сигнала [6], LF – длина цикла ВУ в канальных интервалах.
Утверждение 2. Перемеженная ДП есть упорядоченное множество двоичных символов { d } T, где Т – период перемежения.
Кроме того, совокупность уплотняемых ДП до ВУ, а также ДП до перемежения можно рассматривать как множество упорядоченных элементов. Тогда процессы ВУ и перемежения могут быть описаны соответственно выражениями (1, 2).
, (1)
, 2)
где S 1 (D 1) – упорядоченное множество элементов до процесса обработки, S 2 (D 2) – упорядоченное множество элементов после процесса обработки, 
– порядок расположения элементов множества S 1 (D 1), 
– порядок расположения элементов множества S 2 (D 2), P – оператор переупорядочивания элементов множества S 1 (D 1), N 1= LF – мощность множеств S 1 и S 2; N 2= T – мощность множеств D 1 и D 2. Частным случаем является вариант, когда N 1 =N= 2 m, N 2 =N= 2 m, m =0, 1, 2, …
Из выражений (1, 2) видно, что индексы элементов множеств S 1 (D 1) и S 2 (D 2) связаны оператором переупорядочивания элементов P. Если эти индексы представить в двоичном виде
,
,
то переупорядочивание элементов множества S 1 (D 1) будет заключаться в преобразовании индекса ik путем перестановки его бит (3), а частным случаем оператора P будет оператор перестановки бит π (4).
, (3)
. (4)
В зарубежной литературе операция (3, 4) называется перестановкой бит (Bit Permutation) [4; 7; 8]. А наиболее широкое исследование получили ее варианты (5-10).
а) Реверс бит (Bit Reversal)
,
. (5)
б) Транспозиция бит (Bit Transpose)
,
. (6)
в) Идеальное тасование (Perfect Shuffle)
,
. (7)
г) Тройное идеальное тасование (Triple Perfect Shuffle)
,
. (8)
д) Тасование бит (Bit Shuffle)
, где m – четн.
. (9)
е) Реверс бит половин (Half Bit Reversal)
, где m – четн.
. (10)
Примеры распределений индекса j в зависимости от индекса i рассмотренных перестановок бит представлены на рис. 1.
Рассмотренные операции перестановки бит (5-10) могут быть использованы в основе ВУ и перемежения ДП, что позволит соответственно определенным образом распределить информацию уплотняемых абонентов и рассредоточить расположенные рядом символы.
Оценивание равномерности распределения информации уплотняемых абонентов в переделах цикла ВУ с использованием операций перестановки бит произведено на основе математического ожидания M и дисперсии D индексов jk (где k = 0, 1, …, N -1) от доли выделенного ресурса цикла ВУ CF. (рис. 2, 3, пунктирными линиями отображены границы оценок при CF =100%, точками – зависимости при традиционном подходе к ВУ).
Рисунок 1. Зависимость j от i для операций а) реверса бит,
б) транспозиции бит, в) идеального тасования, г) тройного идеального
тасования, д) тасования бит, е) реверса бит половин при N =256
Рисунок 2. Зависимость M индексов jk от CF при ВУ с использованием
а) реверса бит, б) транспозиции бит, в) идеального тасования, г) тройного
идеального тасования, д) тасования бит, е) реверса бит половин для N =256
Рисунок 3. Зависимость D индексов jk от CF при ВУ с использованием
а) реверса бит, б) транспозиции бит, в) идеального тасования, г) тройного
идеального тасования, д) тасования бит, е) реверса бит половин для N =256
Из рис. 2, 3 видно, что наилучшей равномерности распределения информации уплотняемых абонентов в переделах цикла ВУ возможно достичь при использовании операции реверса бит. Также неплохой равномерностью распределения обладают операции транспозиции бит и тройного идеального тасования.
Анализ результативности перемежения ДП с использованием операций перестановки бит произведен на основе частоты встречаемости расстояния между рассредоточенными (после перемежения) двоичными символами W (| Δj |) для различных значений расстояния между двоичными символами до перемежения | Δi |. Графики зависимостей W (| Δj |) от | Δj | для N =64 и | Δi |=1, 2 представлены на рис. 4, 5.
Рисунок 4. Зависимость W (| Δj |) от | Δj | при перемежении ДП на основе а) реверса бит,
б) транспозиции бит, в) идеального тасования, г) тройного идеального тасования,
д) тасования бит, е) реверса бит половин для | Δi |=1
Из рис. 4 видно, что для канала связи с пакетами ошибок в два двоичных символа наилучших характеристик перемежения (при N =64) возможно достичь при использовании операции идеального тасования, которая рассредоточивает два соседних двоичных символа на почти оптимальное расстояние (половина периода перемежения). Операция реверса бит также рассредоточивает два соседних двоичных символа на оптимальное расстояние, но только в половине случаев. Вместе с тем минимальное расстояние рассредоточения двоичных символов составляет четверть периода перемежения. Операции транспозиции бит, тройного идеального тасования (для N =64, m =6 операция тройного идеального тасования идентична операции транспозиции бит) и реверса половин бит рассредоточивают соседние двоичные символы в большинстве случаев на расстояние, равное восьмой части периода перемежения, что требует применения канальных кодов с более высокой помехоустойчивостью. Использование операции тасования бит для перемежения ДП не целесообразно, так как в половине случаев соседние двоичные символы она не рассредоточивает.
Рисунок 5. Зависимость W (| Δj |) от | Δj | при перемежении ДП на основе а) реверса бит,
б) транспозиции бит, в) идеального тасования, г) тройного идеального тасования,
д) тасования бит, е) реверса бит половин для | Δi |=2
Из рис. 5 видно, что для канала связи с пакетами ошибок в три двоичных символа (при N =64) применение операций идеального тасования и реверса бит половин не целесообразно, потому что они сосредоточивают двоичные символы, стоящие через один символ, вместе в 99% и 25% случаев соответственно. Операции транспозиции бит, тройного идеального тасования в большинстве случаев и операция реверса бит в половине случаев рассредоточивают двоичные символы, стоящие через один символ, на четверть периода перемежения. Таким образом, пакеты в три ошибки позволяют рассредоточить только три операции – реверса бит, транспозиции бит и тройного идеального тасования.
Более качественное оценивание результативности перемежения ДП с использованием операций перестановки бит возможно получить на основе экспериментальных исследований. Тем не менее, проведенный теоретический анализ позволяет заключить, что наибольшей результативностью перемежения обладают операции реверса бит и транспозиции (тройного идеального тасования) бит. Применение первой позволяет производить перемежение ДП по почти случайному закону (рис. 1, а) и рассредоточивать двоичные символы с обратно пропорциональной зависимостью от расстояния между ними. Применение второй – с прямо пропорциональной зависимостью и некоторым неслучайным законом (рис. 1, б).
* * *
Таким образом, рассмотренный подход к временному уплотнению и перемежению ДП на основе математических операций перестановки бит позволяет:
· на этапе ВУ: сократить время ожидания каждого абонента и оптимизировать использование буферной памяти устройств мультиплексирования;
· на этапе перемежения: в некоторой степени адаптировать процесс рассредоточения ошибок к характеристикам каналов связи и канального кодера.
При этом наилучших результатов возможно достичь при использовании операции реверса бит. Именно это и обусловило ее широкое применение на различных этапах формирования сигналов современных систем цифровой связи [5; 9].
Литература
1. Кларк, Дж. мл. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. – М.: Радио и связь, 1987. 392 с.
2. Скляр, Б. Цифровая связь. Теоретические основы и практическое применение. – М.: Издательский дом «Вильямс», 2003. 1104 с.
3. Тамп, В.Л. Динамическое мультиплексирование сигналов с квазиравномерным распределением канальных интервалов / В.Л. Тамп, М.В. Печурин, В.С. Дмитриевский // Наукоемкие технологии. 2009. №1. С. 5-9.
4. Chin, A. Permutations on the Block PRAM / Information Processing Letters 45, 1993. Pp. 69-73.
5. European Patent 1376880 A1. Interleaving / Deinterleaving Device and Method for Communication System, 2004.
6. ITU-T. Vocabulary of Digit Transmission and Multiplexing, and Pulse Code Modulation (PCM) Terms G.701. Helsinki, 1993.
7. Jarvinen, T. Systematic Methods for Designing Stride Permutation Interconnections / Thesis for the degree of Doctor of Technology. Tampere University of Technology, 2004.
8. Petrini, F. k-ary n-trees: High Performance Networks for Massively Parallel Architectures / F. Petrini, M. Vanneschi. In Proceedings of the 11th International Parallel Processing Symposium, IPPS’97, pp. 87-93, Geneva, Switzerland, 1997.
9. United States Patent US 6854072 B2. Apparatus and Method for Providing Turbo Code Interleaving in a Communications System, 2005.
References
1. Clark, J. ml. Coding with correction of mistakes in the systems of digital communication: The lane with English – M.: Radio and communication, 1987. 392 pages.
2. Sklyar, B. Digital communication. Theoretical bases and practical application. – M.: Williams publishing house, 2003. 1104 pages.
3. Tamp, V.L. Dynamic multiplexing of signals with quasiuniform distribution of channel intervals / V.L. Tamp, M.V. Pechurin, V.S. Dmitriyevsky//High technologies. 2009. No. 1. Page 5-9.Chin, A. Permutations on the Block PRAM / Information Processing Letters 45, 1993. Pp. 69-73.
4. European Patent 1376880 A1. Interleaving / Deinterleaving Device and Method for Communication System, 2004.
5. ITU-T. Vocabulary of Digit Transmission and Multiplexing, and Pulse Code Modulation (PCM) Terms G.701. Helsinki, 1993.
6. Jarvinen, T. Systematic Methods for Designing Stride Permutation Interconnections / Thesis for the degree of Doctor of Technology. Tampere University of Technology, 2004.
7. Petrini, F. k-ary n-trees: High Performance Networks for Massively Parallel Architectures / F. Petrini, M. Vanneschi. In Proceedings of the 11th International Parallel Processing Symposium, IPPS’97, pp. 87-93, Geneva, Switzerland, 1997.
8. United States Patent US 6854072 B2. Apparatus and Method for Providing Turbo Code Interleaving in a Communications System, 2005.