9-й Международный симпозиум по электромагнитной совместимости и электромагнитной экологии

Подождите немного. Документ загружается.

221

компонентов и цепей, принадлежащих различным

классам, на одной печатной плате.

Да

Нет

Определение и ввод

исходных данных задачи

проектирования печатных

плат цифровых ЭС

Определение начальных

параметров

эволюционного

алгоритма

Поиск оптимального

решения задачи с

использованием

эволюционного

алгоритма

Оценка оптимальности

полученного решения

Удовлетворяет

ли качество

полученного

результата?

Сохранение полученного

результата

Выбор критериев и

ограничений ЭМС

Предварительный анализ

ЭМС конструктива

печатной платы

Существует

необходимость в

обеспечении

ЭМС?

Выбор конструктивных

критериев и ограничений

Определение приоритетов

критериев оптимизации

Рис.1. Обобщенная методика решения задач

проектирования печатных плат.

Классификация цепей и компонентов цифровых

ЭС может быть проведена по степени их восприим-

чивости к внешним электромагнитным воздействи-

ям, а также по уровню излучаемых электромагнит-

ных полей. В качестве критерия ЭМС задачи компо-

новки предлагается максимизировать количество

компонентов и цепей, размещаемых на одной печат-

ной плате и принадлежащих одному классу или со-

вместимым классам. Рекомендуется также использо-

вать ограничение ЭМС для размещения компонентов

и цепей, принадлежащих несовместимым классам на

различных печатных платах. Использование данного

критерия и ограничения ЭМС при решении задачи

компоновки позволяет распределять компоненты

цепей, наиболее чувствительных к внешнему элек-

тромагнитному воздействию, отдельно от компонен-

тов цепей, излучающих сильные электромагнитные

поля, что, в свою очередь, влечет за собой снижение

перекрестных помех в межсоединениях печатных

плат. Уменьшению помех будет способствовать ус-

тановка печатных плат, содержащих компоненты

чувствительных цепей, в наиболее защищенные от

внешнего электромагнитного воздействия зоны кон-

струкции цифрового ЭС.

При необходимости в снижении помех, связан-

ных с задержкой и расфазировкой сигналов в межсо-

единениях печатных плат, при решении задачи ком-

поновки рекомендуется использовать критерии и

ограничения, позволяющие учитывать временные

параметры функционирования компонентов и цепей.

Кроме того, при поиске оптимального решения

задачи компоновки может быть использован тради-

ционный критерий минимизации межмодульных

соединений. Ограничения задачи компоновки вво-

дятся на следующие конструктивные параметры:

площадь монтажного пространства печатной платы;

количество внешних выводов печатных плат; коли-

чество компонуемых печатных плат.

Для применения критерия и ограничения ЭМС

при решении задачи размещения на монтажной

плоскости печатной платы предлагается определить

множество непересекающихся зон прямоугольной

формы. Для каждого размещаемого компонента ре-

комендуется установить его принадлежность опре-

деленной зоне печатной платы. При решении задачи

предлагается использовать ограничение на размеще-

ние каждого компонента в рамках соответствующей

ему прямоугольной зоны печатной платы. В случае

невозможности использования указанного ограниче-

ния ввиду определенных конструктивных требова-

ний, предлагается использовать критерий минимиза-

ции числа компонентов, размещаемых вне соответ-

ствующих им зон. Размещение компонентов цепей,

чувствительных к внешнему электромагнитному

воздействию, в наиболее защищенных зонах печат-

ной платы позволит снизить риск искажения и воз-

никновения паразитных сигналов в межсоединениях,

что, в свою очередь, способствует повышению ЭМС

и надежности ЭС. Расположение зон, содержащих

компоненты цепей с высоким уровнем излучения

электромагнитных полей, вдали от зон с компонен-

тами чувствительных цепей приведет к снижению

перекрестных помех в межсоединениях печатных

плат.

При решении задачи размещения, в качестве

критериев и ограничений могут учитываться конст-

руктивные параметры печатной платы, а также па-

раметры теплового режима. Кроме того, рекоменду-

ется использовать критерии и ограничения, позво-

ляющие создать благоприятные условия для после-

дующей трассировки межсоединений.

Для повышения устойчивости цифровых ЭС к

внешним электромагнитным воздействиям, а также

снижения уровня излучаемых полей, при решении

задачи трассировки, в качестве критерия ЭМС, пред-

лагается минимизировать площадь контуров, образо-

ванных межсоединениями печатных плат. Использо-

вание данного критерия позволяет уменьшить вели-

чины токов и напряжений, индуцированных в меж-

соединениях контуров при внешнем электромагнит-

ном воздействии, что способствует снижению риска

искажения и возникновения паразитных сигналов.

Уменьшение площади контуров способствует и сни-

жению напряженности электромагнитного поля из-

лучаемого от межсоединений печатных плат. Кроме

критерия ЭМС рекомендуется использовать ограни-

чение на размещение межсоединений цепей, наибо-

лее чувствительных к внешнему электромагнитному

воздействию, во внутренних слоях печатной платы.

222

При решении задачи трассировки также предла-

гается использовать ряд критериев, позволяющих

снизить уровни

внутриаппаратурных помех. Для

уменьшения задержек при распространении сигна-

лов может быть использован критерий минимизации

суммарной длины сигнальных межсоединений. Для

снижения помех, связанных с расфазировкой сигна-

лов, предлагается минимизировать разность между

длинами межсоединений в синхронных цепях. С це-

лью уменьшения отражений сигналов в межсоедине-

ниях рекомендуется минимизировать число меж-

слойных переходов и изгибов трасс. Критерий ми-

нимизации расстояний между параллельными участ-

ками межсоединений может быть использован для

снижения уровня перекрестных помех.

В качестве ограничений задачи трассировки

также могут быть определены:

- ширина и длина отдельных межсоединений;

- расстояние между отдельными межсоедине-

ниями;

- конфигурация отдельных межсоединений;

- группы межсоединений равной длины;

- зоны печатной платы, размещение межсоеди-

нений, в которых является недопустимым;

- слои металлизации для цепей питания и земли;

- приоритетные ориентации межсоединений для

каждого из слоев печатной платы.

При выборе критериев оптимизации, ЛПР уста-

навливает их приоритеты использования в задаче

проектирования печатных плат. В зависимости от

приоритетов, для каждого критерия оптимизации

вычисляется значение весового коэффициента адди-

тивной целевой функции.

Существующие методы и алгоритмы оказыва-

ются неэффективными для решения многокритери-

альных задач проектирования печатных плат, так как

обладают высокой временной сложностью и не по-

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

Ввиду этого, возникает необходимость в разработке

эффективного алгоритма решения задач проектиро-

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

ностью исходных данных, с учетом большого числа

критериев и ограничений.

Для решения многокритериальных задач проек-

тирования печатных плат, в работе предлагается ис-

пользование эволюционных алгоритмов оптимиза-

ции [2]. После выполнения процедуры оптимизации,

с использованием эволюционного алгоритма, ЛПР

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

задачи. При неудовлетворительном качестве осуще-

ствляется повторное решение задачи проектирования

печатных плат. При этом ЛПР может изменить набор

критериев оптимизации, их приоритеты, ограниче-

ния задачи, а также значения управляемых парамет-

ров алгоритма.

На основе предлагаемой методики, а также эво-

люционных алгоритмов оптимизации были разрабо-

таны программные модули решения задач проекти-

рования печатных плат.

По результатам проведенных эксперименталь-

ных исследований методики и эволюционных алго-

ритмов решения задач проектирования печатных

плат предлагаются следующие выводы:

1. Использование эволюционных алгоритмов

при решении многокритериальных задач проектиро-

вания печатных плат, по сравнению с другими мето-

дами и алгоритмами, позволяет достичь высокого

качества результирующих решений, при небольших

временных затратах.

2. Эволюционные алгоритмы обладают линей-

ной временной сложностью, что позволяет приме-

нять их при решении задач с большой размерностью

исходных данных.

Заключение

Основными результатами работы являются:

1. Методика решения задач проектирования пе-

чатных плат, с учетом критериев и ограничений

ЭМС.

2. Критерии и ограничения ЭМС для задач про-

ектирования печатных плат и обоснование необхо-

димости их использования для снижения электро-

магнитных помех.

3. Эволюционные алгоритмы решения задач

проектирования печатных плат, с учетом большого

числа критериев и ограничений.

4. Программные модули решения задач проек-

тирования печатных плат, разработанные на основе

предлагаемой методики и эволюционных алгорит-

мов.

5. Результаты экспериментальных исследова-

ний, подтверждающие эффективность применения

предлагаемой методики и эволюционных алгоритмов

для решения задач проектирования печатных плат

современных цифровых ЭС.

Литература

1. Кечиев Л.Н. Проектирование печатных плат

для цифровой быстродействующей аппаратуры.- М.:

ООО «Группа ИДТ», 2007. – 616 с.

2. Емельянов В.В., Курейчик В.В., Курейчик

В.М. Теория и практика эволюционного моделиро-

вания. - М.: ФИЗМАТЛИТ, 2003. – 432 с.

223

ИССЛЕДОВАНИЕ ВЛИЯНИЯ СВЕРХКОРОТКИХ

ЭЛЕКТРОМАГНИТНЫХ ИМПУЛЬСОВ НА ПРОЦЕСС ПЕРЕДАЧИ

ДАННЫХ В СЕТЯХ ETHERNET

Р.

В.

ИРИЧЕК

ОССИЯ

Л.

А.

АТАЛОВ

ОССИЯ

ФГУП ЦентрИнформ, e-mail: r.kirichek@center-inform.ru

Аннотация. В статье представлены основные результаты теоретических исследований влияния

сверхкоротких электромагнитных импульсов, наводимых в физической среде Ethernet в результате

силовых электромагнитных воздействий на процесс передачи данных в сетях Ethernet. Установлена

зависимость вероятности ошибок на канальном уровне и снижения производительности сети от па-

раметров сверхкоротких электромагнитных воздействий.

Abstract. The article presents theoretical consideration the impact of very short electromagnetic pulses

induced in the physical environment as a result of Ethernet power electromagnetic influences on the process

of transmitting data in the Ethernet. The dependence of error probability at the link layer and network

efficiency degradation under the electromagnetic influences is established.

Введение

В последние годы стремительно развиваются

технические средства, способные генерировать мощ-

ные сверхкороткие электромагнитные импульсы (СК

ЭМИ). В связи с этим одним из признанных видов

угроз нарушения функционирования процесса пере-

дачи данных в сетях доступа и сетях в помещении

пользователя автоматизированных систем, стали

преднамеренные электромагнитные воздействия [1].

В настоящее время Ethernet – наиболее распро-

страненная технология передачи данных в компью-

терных сетях [2]. Экономичность, скорость, а также

простота, легкость использования и известность

Ethernet являются большим плюсом при построении

современных сетей.

В настоящее время предпринимаемые меры по

кибербезопасности в сетях связи ориентированы, в

основном, на защиту на программном уровне [3].

Работы по защите от преднамеренных электромаг-

нитных воздействий находятся на начальном этапе.

Развиваемый в настоящей работе расчетный аппарат

может быть использован при развертывании этих

работ.

Сверхкороткие электромагнитные импульсы

оказывают деструктивное воздействие через эфир

или физическую среду передачи данных, нарушая

процесс обмена электрическими сигналами. Наибо-

лее распространенные стандарты: Fast Ethernet и Gi-

gabit Ethernet для спецификаций 100Base-TX и

1000Base-T соответственно – не используют алго-

ритмы кодирования с коррекцией ошибок. Поэтому

искажение лишь одного символа в кадре уже ведет

для этих стандартов к ошибке приема всего кадра.

Основные положения

Рассмотрим периодически повторяющаяся

импульсная помеха, с длительностью импульса τ и

периодом повторения импульса Т. Частота

повторения импульсов равна, очевидно, f=1/T.

Форма импульса задается функцией g(t)=V(t)/V

, где

– амплитуда помехи.

Представим периодически повторяющуюся

помеху как эквивалентный гауссов шум [4].

Предположим, что исходный импульс биполярный,

так что можно считать среднее напряжение гауссова

шума нулевым. Дисперсию V

найдём из равенства

энергий:

2 2 2

( )

g m

V fV g t dt

∫

(1)

Будем считать, что амплитуда V

выбрана так,

что интеграл в (1) равен длительности импульса τ.

Тогда получаем:

g m

V V f

(2)

Авторами была усовершенствована

математическая модель, предложенная ранее

А.Колбергом, Л.Здуховым, Ю.Парфеновым и

Б.Титовым [4]. Эти авторы разработали модель,

позволяющую оценить вероятность неправильной

передачи кадра с данными в зависимости от

параметров сети и характеристик помехи. Основное

положение, от которого они отталкивались, состоит

в том, что если напряжение импульсной помехи

накладывается на информационные символы, то

логическая единица может быть воспринята как

логический нуль или логический нуль может быть

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

называется единичным сбоем. Исходя из

представления повторяющейся импульсной помехи в

виде эквивалентного гауссовского шума,

вероятность сбоя оценивается с помощью

следующего соотношения:

∫

−

∞−

−⋅=−=

))erf(z/(.)dλ/λ(

(z)

P 21502exp

(3)

где z=A/V

– отношение сигнал/шум;

224

)(xerf

– функция ошибок.

Вероятности неправильной передачи пакета

данных, в условиях воздействия периодически

повторяющейся импульсной помехи определяется

соотношением:

1 (1 )

P P

= − −

(4)

где P

– вероятность единичного сбоя, зависящая

только от отношения сигнал-шум;

m – число символов в кадре, подвергаемых

воздействию.

Рис. 1.

Зависимость вероятности искажения кадра P с

данными от числа символов, подверженных

воздействию m.

Важно отметить, что в данной постановке

задачи m не зависит от символьной скорости R.

Межсимвольный интервал и символьная скорость –

взаимно обратные величины. Поэтому имеем

m R N f N

τ τ

= × × =

(5)

где N – число символов в кадре. Величину D = fτ

называют коэффициентом заполнения [5].

Однако, соотношение (3) корректно лишь для

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

например, манчестерского кода. Манчестерский код

используется в сетях Ethernet со скоростью передачи

10 Мбит/с (спецификация 10Bаsе-Т). Авторами

предложено применить приведенный способ

вычисления к различным вариантам кодирования,

используемым в современных высокоскоростных

сетях связи. При этом формула (4) сохраняется.

Таким образом, различия в алгоритмах кодирования

будут сказываться лишь на зависимости вероятности

единичного сбоя P

от параметров помехи.

Зависимость вероятности искажения кадра с

данными от m приведена на рис.1. Кривая 1

соответствует P

= 0.2, кривая 2 соответствует P

0.5, кривая 3 соответствует P

= 0.8. Из формул (1-2)

(5) следует, что в окончательном выражении для

вероятности искажения кадра P будут участвовать

только два параметра: коэффициент заполнения D и

определенная выше амплитуда V

Fast Ethernet

Согласно спецификации [6], на физическом

уровне используется кодирование MLT-3, в котором

три уровня сигнала: «-1», «0», «+1». Логической

единице соответствует обязательный переход с

одного уровня сигнала на другой. При передаче

логического нуля изменение уровня линейного

сигнала не происходит. Для учета этого

обстоятельства при расчетах необходимо знать

вероятности появления символов -1, 0, +1. Их

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

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

многочисленных вариантов реальных сигналов [7] и

составляют 0,25; 0,5; 0,25 соответственно.

Кодирование MLT-3 не является

помехозащищённым. Поле контрольной суммы

кадра (FCS — Frame Check Sequence) позволяет

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

повреждены. Искажение только одного символа в

кадре ведёт к ошибке приема всего кадра.

Предположим, пакет передаваемых данных

состоит из N битов (которые после избыточного

кодирования превратятся в 5N/4 троичных

символов). Будем рассматривать представляющую

практический интерес ситуацию, когда длительность

импульса помехи совпадает с межсимвольным

интервалом: τ = 1/R. Тогда m = f(N/R) битов будут

подвержены воздействию. Вероятность того, что

подверженный воздействию бит информации будет

воспринят правильно, равна Q=1-P

. С учетом

вероятности появления символов -1, 0, +1 получаем,

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

неправильной передачи кадра с данными:

2121.0

75.0

202.1

25.05.01

erf

erfP





































+−−=

, (6)

где D=f/R. На рис. 2 представлена соответствующая

Рис. 2.Зависимость вероятности искажения кадра

данных P от коэффициента заполнения импульсов D.

зависимость. Кривая 1 соответствует амплитуде

импульсов V

= 0.5, кривая 2 соответствует V

= 0.7,

кривая 3 соответствует V

= 1. Видно, что при

некотором значении коэффициента заполнения

искажаются практически все пакеты, как и в случае

манчестерского кода [5].

225

Gigabit Ethernet

Согласно спецификации [6] стандарта Gigabit

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

1000BASE-T используется 5-уровневое импульсно-

амплитудное кодирование PAM-5: –1, –0.5, 0, +0.5,

+1. Вероятность их появления составляют 0,19; 0,21;

0,15; 0,23; 0,22 соответственно.

Вероятность единичного сбоя с учетом

найденных вероятностей появления символов, может

быть определена по следующей формуле:

1.75 0.75 0.25 1.25

0.2 4

2 2 2 2

g g g g

P erf erf erf erf

V V V V

 

       

 

       

= − − − −

       

 

       

 

, (7)

где V

- напряжение эквивалентного гауссова шума.

На рис. 3 показана зависимость P

от V

Рис. 3. Вероятность единичного сбоя P

для

стандарта Gigabit Ethernet как функция напряжения

эквивалентного гауссова шума.

Выводы

Рассмотрев асимптотику функции ошибок при

больших и малых значениях аргумента можно

сделать два имеющих практическую ценность

вывода:

1. При больших аргументах x ≥ 3, erf(x) ≈ 1.

Легко показать, что искажаются практически все

пакеты, начиная с отношения сигнал-шум

V f



(8)

2. Современные Web-приложения очень

требовательны к качеству обслуживания в

современных высокоскоростный сетях. Поэтому

доля потерянных кадров, которую можно

отождествить с вероятностью искажения одного

кадра, должна быть очень малой. В рекомендациях

RFC 1540, 1541 говорится, что ее значение на

сетевом уровне не должно превышать 10

-12

– 10

-9

Обозначая критическую долю потерянных пакетов ε

и пользуясь ассимптотикой функции ошибок при

малых аргументах, получаем область на плоскости m

- S, где m – число символов, подверженных

воздействию, S – отношение сигнал – шум, в которой

P ≤ ε:

0.25 ln ln ln

S S m

− − + ≤ (9)

На

рис

. 4

показана

такая

область

для

=10

-9

Рис

. 4.

Соотношение

(9)

для

= 10

-9

Точки

лежащие

ниже

кривой

соответствуют

области

устойчивости

Выражения

(6), (7), (8)

можно

использовать

для

анализа

эффективности

воздействия

сверхкоротких

электромагнитных

импульсов

на

процесс

передачи

данных

сети

Ethernet.

Они

также

позволяют

сформулировать

рациональные

требования

оборудованию

для

натурных

испытаний

сетей

передачи

данных

реализованных

использованием

технологии

Ethernet,

на

устойчивость

преднамеренным

электромагнитным

воздействиям

Литература

Ларионенко

Разработка

требований

средствам

защиты

локальных

вычислительных

се

тей

от

деструктивного

воздействия

сверхкороткоим

пульсного

электромагнитного

излучения

автореф

дис

канд

технич

наук

МИЭМ

. -

МИЭМ

, 2010. -

Zhuo Xu,

Designing and Implementing IP/MPLS-

Based Ethernet Layer 2 VPN Services: An Advanced

Guide for VPLS and VLL, Wiley Publishing Inc, 2009.

Жуков

Стохастические

методы

сред

ства

защиты

информации

компьютерных

системах

сетях

КУДИЦ

ПРЕСС

, 2009.

Parfenov Y.V.; Kohlberg I.; Radasky W.A.; Titov

B.A.; Zdoukhov L.N., The probabilistic analysis of im-

munity of a data transmission channel to the influence of

periodically repeating voltage pulses, 19th International

Zurich Symposium on EMC, 2008.

I. Kohlberg and R. Carter, “Some theoretical con-

siderations regarding the susceptibility of information

systems to unwanted electromagnetic signals”, Proc. of

the 14th Int. Zurich Symposium on EMC, Zurich, Swit-

zerland, February 20–22, 2001, p.41–46.

IEEE 802.3-2008 Standard for Information tech-

nology-Specific requirements - Part 3: CSMA/CD and

Physical Layer Specifications: Section two and Section

three.

Баталов

Киричек

Лазарев

Ве

роятностные

характеристики

электрических

сигна

лов

Fast Ethernet //

Естественные

технические

нау

ки

. -2010. -

№

226

ТЕХНИЧЕСКИЙ АНАЛИЗ СИГНАЛОВ ПРИ МОНИТОРИНГЕ

ЭЛЕКТРОМАГНИТНОЙ ОБСТАНОВКИ

А. Ф. КРЯЧКО, РОССИЯ, К. Ю. РЮМШИН, РОССИЯ, И. Е. ЗАЙЦЕВ, РОССИЯ

Санкт-Петербургский государственный политехнический университет, Alex_k34.ru@mail.ru

Аннотация. Рассматриваются проблемы мониторинга электромагнитной обстановки для

решения задач по повышению помехоустойчивости систем обработки информации в процессе

экологического мониторинга.

Abstract. Some problems of supervision the electromagnetic environment to solve the task of

improving the noise stability of data processing systems in environmental monitoring.

Общие сведения о решении системы

линейных алгебраических уравнений при

техническом анализе сигналов

При решении задач технического анализа

цифровых последовательностей в системах связи и

передачи данных часто возникает необходимость

решения системы линейных алгебраических

уравнений (СЛАУ).

Множество всех кодовых слов линейных

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

где - коэффициенты (для двоичных кодов

В случае представления кодовых слов в виде

строк матрицы размера , имеем

порождающую матрицу кода :

При представлении кода в систематическом

виде порождающая матрица записывается

следующем образом:

В этом случае правая часть матрицы содержит

коэффициенты уравнений проверки на четность:

которые в отсутствие ошибок при приеме

выполняются для всех кодовых слов данного кода.

Поскольку код однозначно определяется своей

порождающей матрицей или коэффициентами

уравнений проверки на четность, то для его

идентификации достаточно определить значения

этих коэффициентов , :

Аналогично можно составить еще

систему линейных уравнений относительно

коэффициентов , , . Отметим,

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

коэффициенты неизвестных и отличаются только

столбцом свободных членов.

Система имеет единственное решение [1] в

том случае, когда определитель матрицы,

составленной из коэффициентов при переменных в

линейно независимых уравнениях, отличен от

нуля:

Тогда решение системы может быть найдено

по формулам Крамера:

где – определитель, полученный из заменой j-

гo столбца столбцом свободных членов.

На практике формулы Крамера используются

редко ввиду быстрого роста с увеличением

227

сложности вычисления значений соответствующих

определителей. Значительно чаще используются

разнообразные модификации метода Гаусса для

решения систем линейных уравнений.

Метод Гаусса подробно описан в литературе

[1], и суть его заключается в последовательном

исключении неизвестных из уравнений системы.

Для того, чтобы решить систему уравнений

необходимо выписать расширенную матрицу,

включающую помимо коэффициентов при

неизвестных столбец свободных членов. Затем над

строками этой матрицы произвести элементарные

преобразования:

 изменения порядка строк, что

соответствует изменению порядка следования

уравнений;

 умножение строки на любые отличные от

нуля числа и прибавление к любой строке любой

другой ее строки, умноженной на любое число. С

помощью таких преобразований каждый раз

получается расширенная матрица новой системы,

равносильной исходной.

Поскольку все систем линейных

алгебраических уравнений отличаются только

столбцами свободных членов, они могут решаться

одновременно, для чего в расширенную матрицу

включают сразу все столбцы свободных членов

уравнений.

Процедура решения разбивается на два этапа,

обычно называемые прямым и обратным ходом

решения СЛАУ.

Вычислительные формулы для решения

системы линейных алгебраических уравнений

методом Гаусса имеют следующий вид. Прямой

ход:

Обратный ход реализуется в соответствии с

выражением:

Чтобы производить вычисления в

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

необходимо, чтобы все ведущие элементы ,

, были отличны от нуля. Для того, чтобы

избежать деления на нуль, обычно реализуют

алгоритм решения СЛАУ по методу Гаусса с

выбором ненулевого ведущего элемента по столбцу

(иногда по всей матрице в целом). При этом часто

для удобства вычислений делают перестановку

уравнений.

В случае решения СЛАУ в двоичном поле

отпадает необходимость в операциях

деления и умножения, а все преобразования

производятся только путем сложения строк

расширенной матрицы.

Длина линейной зависимости для сверточных

кодов превышает , так как проверочный символ

формируется с помощью не только текущего, но и

нескольких предыдущих символов. Длина

линейной зависимости для сверточного кода

называется длиной кодового ограничения

, где – длина регистра кодера, которая

определяет количество информационных символов,

участвующих в формировании проверочного.

Таким образом, в процессе технического

анализа сверточных кодов можно определить такие

его параметры, как , и .

Выявленные особенности процесса

решения системы линейных алгебраических

уравнений

Для того, чтобы система линейных уравнений

была определенной, т.е. имела единственное

решение, должны выполняться следующие

условия:

1) ,

2) из уравнений должны быть линейно

независимы.

Теорема 1

Вероятность того, что произвольных

двоичных последовательностей являются

независимыми определяется выражением:

Теорема 2

Последовательность является убывающей

ограниченной последовательностью ,

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

можно определить как , при этом

для любого , где , а

, где , следовательно,

228

для любого .

Доказательство

Для того, чтобы получить приближенное

значение произведения (1) рассмотрим бесконечное

произведение следующего вида:

и докажем сходимость числового

ряда

по признаку Даламбера [2].

Преобразуем бесконечное произведение к

виду:

Необходимым и достаточным условием

сходимости бесконечного произведения является

сходимость числового ряда:

Рассмотрим числовой ряд (3). Данный

числовой ряд является знакопостоянным, все его

слагаемые – отрицательные величины. Данный ряд

можно сделать положительным, вынеся минус за

знак суммы. Для доказательства сходимости ряда

по Даламберу рассмотрим предел:

то величины в числителе и знаменателе предела

являются бесконечно малыми, следовательно,

имеет место эквивалентность .

Здесь . Тогда ряд (4) примет вид:

Таким образом, поскольку ряд по Даламберу

сходится, то сходится и бесконечное произведение.

Его значение можно вычислить приближенно с

помощью частного произведения :

Таким образом: . Проведем оценку

абсолютной погрешности с помощью критерия

Коши. Если , то абсолютная

погрешность .

График зависимости вероятности линейной

независимости строк в матрице СЛУ размерности

от приведён на рисунке 1.

0 5 10 15 20 25 30 35 40 45 50

0.25

0.3

0.35

0.4

0.45

0.5

Рис.1

Из графика, представленного на рис. 1, можно

однозначно заключить, что с ростом размерности

матрицы величина функции вероятности линейной

независимости кодовых слов быстро стремится к

величине . Расчетами установлено, что

Таким образом, вероятность нахождения

единственного решения произвольной СЛУ не

будет превышать

На рис. 2 представлено для матриц ,

и количество всех двоичных

комбинаций матриц и число сходящихся и

несходящихся из них. Приведение данных для

других размерностей матриц затруднительно с

точки зрения вычислительных и временных затрат,

так для матриц общее количество двоичных

комбинаций матриц составит , для

– и т.д.

Рис. 2.

Представленные на рис. 2 результаты

аналитических вычислений подтверждают

выражение (1) и сформулированные теоремы.

 

229

Следовательно, можно утверждать, что вероятность

решения СЛУ, а соответственно и количество

сходящихся матриц, для матриц других

размерностей так же будет удовлетворять

выражению (1).

Стандартная оценка методов решения

системы линейных алгебраических уравнений

Широкое распространение различных

модификаций метода Гаусса в качестве

алгебраического метода технического анализа

линейных кодов [3] обусловлено тем, что его

реализация требует приемлемого качества

операций для большинства используемых на

практике кодов. Описанный алгоритм требует

проведения приблизительно

операций. При этом требуемый объем памяти

пропорционален , для решения СЛУ по

формулам Крамера требуется произвести

операций.

В таблице 2 приведено число арифметических

действий при решении СЛУ по формулам Крамера

и методом Гаусса.

Табл.1

формулы

Крамера

метод

Гауса

364

2885

123

3.6х10

8х10

6.7х10

4.5х10

2048

7.2х10

5900

5.6х10

Из таблицы 1 видно, что даже для часто

используемых кодов Рида-Соломона с длиной

кодового слова в 2040 двоичных символов

необходимый объем вычислений с помощью

современных ЭВМ может быть выполнен за

приемлемое время.

Существенным недостатком алгебраического

метода является его чувствительность к ошибкам в

канале связи. Поскольку все комбинации ошибок

кратности меньшей не являются кодовыми

словами, то наличие ошибочных символов в

анализируемых кодовых словах приведет к

появлению дополнительных линейно независимых

строк матрицы. Это приведет к тому, что даже

единичный ошибочный символ делает

невозможным определение истинной структуры

кода. Если матрица содержит символов кода,

то все они должны быть приняты безошибочно.

Вероятность безошибочного приема

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

малых . Так, при для кода БЧХ (31, 26)

допустимая вероятность ошибки в канале связи не

больше, чем , а для кода РС (255, 239) в

поле с длиной кодового слова

двоичных символов – .

В том случае, если СЛАУ не сходится,

предлагается не набирать новые данные для

составления новой СЛАУ, а после приведения

матрицы к ступенчатому виду заменить последнюю

(нулевую) строку новой строкой данных и

произвести вычисления заново.

Проведённый анализ показал, что количество

необходимых строк, которое нужно дописать, не

зависит от размерности матрицы. Графики,

иллюстрирующие количество дописанных строк

для матриц различной размерности, представлены

на рис. 3. В них введены следующие обозначения: s

– сколько раз применялась процедура добавления

строки, S – количество матриц, потребовавших

добавления

строк для получения

линейно

независимых строк матрицы, при 1000 испытаний.

Рис. 3.

230

ВЫВОД

Эффективность и даже работоспособность

существующих методов технического анализа,

базирующихся на решении СЛАУ недостаточны.

Это приводит к появлению различных

модификаций и изменений в методах решения,

которые по сути своей в незначительной степени

улучшают характеристики данных методов, в

критической степени зависящих как от характера

анализируемых кодовых последовательностей, так

и от возникающих вследствие наличия шумов в

канале связи ошибок при приеме кодовых

символов.

Литература

1. Воеводин В. В., Кузнецов Ю. А. Матрица и

вычисления. – М.: Наука, 1984. – 318 с.

2. Фихтенгольц Г.М. Курс дифференциального

и интегрального исчисления. Т.3. – М.: Наука, 1966.

– 656 с.

3. Кульбак С. Теория информации и статистика.

– М.: Наука, 1967. – 409 с.