Надежность информационных систем

Конспект лекции по дисциплине «Надежность информационных систем»
ОСНОВНЫЕ ЭЛЕМЕНТЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ
Основные определения и термины
Возникновение отказов в информационных системах зависит от разных факторов и носит случайный характер. Поэтому для количественной оценки различных характеристик систем используются вероятностные методы.
В теории вероятностей случайной называется величина, которая в результате опыта может принять
то или иное значение, предугадать которое заранее и достоверно невозможно.
Событием в теории вероятностей считается всякий факт, который в результате опыта может произойти, а может и не произойти.
Для количественного сравнения между собой событий по степени их возможности используется
определенное число, которое тем больше, чем более возможно событие. Такое число называется вероятностью события.
В практике о вероятности события судят по частоте его появления. Если
в n опытах событие А появилось m раз, то его частота или статистическая вероятность может быть определена соотношением
.
Невозможным называется событие, которое заведомо не произойдет. Вероятность невозможного
события равна нулю.
Достоверным называется событие, которое обязательно произойдет. Вероятность достоверного события равна единице.
Вероятность произвольного случайного события изменяется от нуля до единицы.
Если случайное событие имеет очень малую вероятность, то практически можно считать, что в единичном опыте это событие не наступит. Очень малая вероятность – это значения, заключенные между 0,01 и
0,05. Это свойство называется принципом практической невозможности маловероятных событий.
При неограниченном увеличении числа опытов статистическая вероятность сходится по вероятности
к математической, т. е. частота с вероятностью сколь угодно близкой к единице, приближается к математической
вероятности Р(А).
Если исходы (результаты) испытаний единственно возможны и равновозможны, математическая вероятность события А может быть вычислена по формуле:
,
где n – общее число равновозможных элементарных исходов испытаний;
m – число благоприятных исходов, в которых появляется событие А.
При вычислении величин m и n используется теория сочетаний.
Число сочетаний из m элементов по n вычисляется по любой из двух формул:
,
(2.1)
.
(2.2)
Примеры:
;
;
.
Гипергеометрическое распределение
При решении задач контроля качества продукции используется гипергеометрическое распределение
.
(2.3)
Из группы в n элементов, состоящих из m элементов одного типа и (n – m) элементов другого типа,
берется наугад группа из r элементов. Определяется вероятность того, что среди r элементов будет k элементов первого типа.
Основные теоремы теории вероятностей
Несколько событий называют несовместными в данном опыте, если никакие два из них не могут
появиться вместе.
Теорема сложения утверждает, что если события A и B несовместны, то вероятность появления
одного из них, безразлично какого, равна сумме вероятностей этих событий
Следствие.
Вероятность появления одного из нескольких попарно несовместимых событий, безразлично какого, равна сумме вероятностей этих событий.
Во многих реальных ситуациях событие А может произойти вместе с одним из событий Н1, Н2, …,
Нn, образующих полную группу событий. Эти события называются гипотезами.
Безусловная вероятность P(A) события А вычисляется как сумма произведений вероятности каждой
гипотезы на условную вероятность события при этой гипотезе.
(2.4)
Данная формула называется формулой полной или средней вероятности.
Пусть имеется полная группа несовместных гипотез Н1, Н2, …, Нn. Вероятности этих гипотез до
опыта известны и равны соответственно
,
…,
. Произведен опыт, в результате которого наблюдается появление некоторого события А. Условные вероятности гипотез после опыта
определяются по формуле Бейеса.
.
(2.5)
(i = 1, 2, ..., n).
Формула Бейеса позволяет переоценить вероятности гипотез после того, как становится известен
результат испытания, в итоге которого появляется событие А. Если в результате испытания прибор вышел
из строя, гипотезы Н1 и Н2 становятся невозможными. Необходимо выяснить и устранить причины отказа
прибора.
Расчет вероятностей при многократных испытаниях
Несколько опытов называют независимыми, если вероятность того или иного исхода каждого из
опытов не зависит от исходов других опытов.
Пусть вероятность появления события A во всех независимых опытах одна и та же и равна р. В таком случае, вероятность появления события A в n опытах m раз определяется по формуле Бернулли:
(2.6)
Если число испытаний велико, а вероятность появления события Р в каждом испытании очень мала,
пользуются формулой Пуассона:
,
где m – число появлений события в n испытаниях;
(2.7)
– среднее число появлений события в n испытаниях.
Формула Пуассона именуется законом редких явлений.
Если число независимых опытов n в формуле Бернулли велико, пользуются асимптотической формулой Лапласа:
,
(2.8)
где
Если вероятность p наступления события А в каждом испытании постоянна и отличается от 0 и 1, то
вероятность
того, что событие А появится в n испытаниях от К1 до К2 раз, приближенно
равна определенному интегралу:
(2.9)
где
и
– интегралы Лапласа, величины интегралов определяются по таблице.
Простейший поток событий
Потоком событий называется последовательность событий, которые наступают в случайные моменты времени.
Простейшим (Пуассоновским) называют поток событий, обладающий свойствами стационарности,
отсутствия последействия, ординарности.
Свойство стационарности состоит в том, что вероятность появления событий не зависит от выбора
отсчета времени.
Свойство отсутствия последействия заключается в том, что предыстория потока не сказывается на вероятности появления события в ближайшем будущем.
Ординарность потока означает, что вероятность появления двух событий одновременно отсутствует
Интенсивностью потока  называется среднее число событий, которые появляются в единицу времени.
Если интенсивность потока постоянна, то вероятность появления К событий простейшего потока за
время t определяется формулой Пуассона:
(2.10)
Законы распределения случайных величин
Случайные величины могут быть дискретными или непрерывными.
Дискретной называют величину m, принимающую конечное или счетное число значений.
Законом распределения дискретной случайной величины называется соотношение, устанавливающее связь между возможными значениями случайной величины и вероятностями их появления. Закон распределения может быть задан в табличной форме. Например:
X
2
9
7
6
p
0.5
0.2
0.2
0.1
Непрерывной является величина, которая может принимать любое значение из некоторого конечного промежутка. Число возможных значений непрерывной случайной величины n бесконечно. Вероятность
того, что непрерывная величина примет определенное значение, равна нулю.
, так как n  .
Поэтому интегральной функцией распределения называется функция вида
Функция распределения существует как для дискретных, так и для непрерывных величин и характеризует вероятность события Х < x, где х – текущая переменная.
Свойства функции распределения.
1. F(x) – возрастающая функция.
2.
.
3. Если возможные значения случайной величины принадлежат интервалу [a, b], то F(x) = 0 при x
 a, F(x) = 1 при x  b.
Производная интегральной функции называется дифференциальной функцией распределения,
плотностью распределения или плотностью вероятностей. Плотность распределения существует только для
непрерывных случайных величин.
Каждый закон распределения представляет собой некоторую функцию, которая полностью описывает
случайную величину с вероятностной точки зрения.
Однако на практике достаточно указать параметры, характеризующие в сжатой форме случайную величину. Это математическое ожидание и дисперсия. Для дискретной величины математическое ожидание –
это сумма произведений всех возможных значений случайной величины на вероятность этих значений.
,
для непрерывной величины
(2.11)
,
(2.12)
где
– плотность распределения величины х.
Дисперсией (рассеянием) дискретной случайной величины называют математическое ожидание
квадрата отклонения случайной величины от ее математического ожидания.
.
(2.13)
Пусть случайная величина задана законом распределения
Х
x1
x2
p
p1
p2
По определению дисперсии
….
….
xn
pn
(2.14)
Для непрерывной случайной величины
.
Среднеквадратичное отклонение случайной величины
(2.15)
.
(2.16)
На практике приходится определять численные характеристики случайной величины по ограниченному объему статистических данных.
Статистическое математическое ожидание (среднее значение):
,
(2.17)
где n – количество экспериментальных данных.
Статистическая дисперсия:
.
(2.18)
Возможно получить еще одну формулу для вычисления дисперсии:
2.1
Еще знаменитый астроном-наблюдатель Тихо Браге (1546 – 1601) обратил внимание на то, что точность измерений значительно повышается, если произвести несколько измерений и взять из них среднее
арифметическое. Этот эмпирический факт объясняется теоремой Чебышева. Теорема Чебышева утверждает:
если x1, x2, … , xn – попарно независимые случайные величины, имеющие одно и то же математическое ожидание М и если дисперсии этих величин равномерно ограничены (не превышают постоянного числа С), то,
как ни мало  > 0, вероятность неравенства
це, если число случайных величин достаточно велико.
будет сколь угодно близка к едини-
Сущность теоремы Чебышева состоит в том, что при достаточно больших количествах измерений
их среднее арифметическое мало отличается от истинного значения измеряемой величины. Истинное значение равно математическому ожиданию величины.
На
теореме
Чебышева
основан
выборочный
метод,
суть
которого
состоит
в том, что по сравнительно небольшой случайной выборке судят о всей совокупности исследуемых объектов. Например, о качестве зерна судят по небольшой его пробе. Число наудачу отобранных зерен мало по
сравнению со всей массой зерна, но само по себе велико.
Обработка результатов измерений
Пусть над случайной величиной Х производится ряд независимых опытов (наблюдений). В каждом
из этих опытов случайная величина Х принимает определенное значение. Совокупность наблюдаемых значений величины называется простым статистическим рядом. Оформляется ряд в виде таблицы, в первой
строке которой стоит номер опыта, а во второй – наблюдаемое значение случайной величины.
Например, испытываются 16 приборов, и фиксируется время работы прибора до выхода его из
строя.
По
результатам
опыта
строится
табл.
2.1,
где
в первой строке записывается номер прибора, во второй строке – время работы его Тi в часах.
Таблица 2.1
№
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Тi,ч
2
4
1
8
60
50
40
10
15
20
28
30
35
100
80
70
Ряд, записанный в порядке возрастания случайной величины, называется вариационным. В табл. 2.2
приведен вариационный ряд, полученный из табл. 2.1.
№
Тi, ч
Таблица 2.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
8
10
15
20
28
30
35
40
50
60
70
80
100
2
4
При большом числе наблюдений простой статистический ряд становится слишком громоздким. Для
большей наглядности и компактности статистический материал подвергается дополнительной обработке.
Строится статистический ряд. Диапазон наблюдаемых значений величин вариационного ряда делят
на интервалы или разряды. Подсчитывают количества значений mi, приходящихся на каждый i-й разряд. Это
число делится на общее число наблюдений n. Находится статистическая вероятность
, соответствующая данному разряду. Длины разрядов чаще всего берут одинаковыми. В табл. 2.3 представлен статистический ряд, полученный из табл. 2.2.
В первой строке таблицы записывают интервалы времени t в часах. Во второй строке – число сломавшихся приборов в данном интервале – mi. В третьей строке – статистическая вероятность в данном интервале –
.
Таблица 2.3
t, ч
mi
0-20
7
7/16
20-40
4
4/16
40-60
2
2/16
60-80
2
2/16
80-100
1
1/16
Математическое ожидание и дисперсия статистического материала, представленного в виде статистического ряда, определяются по формулам:
,
(2.20)
,
где
(2.21)
– представитель разряда: среднее значение случайной величины в данном разряде;
– частота или статистическая вероятность разряда;
К – число разрядов.
ОСНОВЫ ТЕОРИИ НАДЕЖНОСТИ СИСТЕМ
Термины и определения в области надежности
Под надежностью понимают свойство сохранять во времени в установленных пределах значения
всех параметров, характеризующих нормальную работоспособность объекта. В понятие надежности входят
такие свойства объекта, как безотказность, долговечность, ремонтопригодность и сохраняемость.
Полная или частичная утрата работоспособности прибора называется отказом. Свойство прибора
сохранять работоспособность в течение заданного времени в определенных условиях эксплуатации называется безотказностью.
Отказы могут быть различного вида и по разным причинам. Внезапный отказ возникает в результате скачкообразного изменения одного или нескольких основных параметров из-за скрытого дефекта. Постепенный отказ является результатом постепенного изменения этих параметров, например, за счет старения.
Полный отказ делает невозможным дальнейшее использование элемента. Частичный отказ позволяет хотя
бы частично использовать элемент. Причинами отказов могут быть ошибки или несовершенство конструкции, нарушения или несовершенства технологического процесса изготовления, а также нарушения правил
эксплуатации и непредусмотренные внешние воздействия. Соответственно, различают технологические,
конструкционные и эксплуатационные отказы.
Долговечность (срок службы) определяется обычно тем, что главный параметр (или несколько параметров) с течением времени ухудшается, т. е. значение его становится минимально допустимым. Тогда элемент подлежит замене.
Ремонтопригодность является свойством элемента, характеризующим его приспособленность к
предупреждению, обнаружению и устранению отказа.
Сохраняемость – это свойство элементов оставаться работоспособными в процессе хранения и
транспортировки.
В зависимости от конкретных систем и условий их эксплуатации, эти свойства могут иметь различную относительную значимость.
Основные показатели надежности невосстанавливаемых (неремонтируемых) систем
Для невосстанавливаемых систем, чаще всего, используются четыре показателя надежности: вероятность безотказной работы P(t), плотность вероятности отказов (частота отказов) f(t), интенсивность отказов λ(t), среднее время безотказной работы (средняя наработка на отказ) T0.
Вероятность безотказной работы P(t) есть вероятность того, что время работы системы до отказа
окажется больше заданного времени t.
,
(3.1)
где Т – случайное время работы системы до отказа или наработка на отказ;
– интегральная функция распределения случайной величины Т (T < t).
Иногда пользуются понятием вероятности отказов Q(t):
.
(3.2)
Если P(t) – надежность системы, то Q(t) – ненадежность системы.
Плотность вероятности, или частота отказов, является дифференциальной функцией распределения.
.
(3.3)
Интенсивность отказа λ(t) – это отношение плотности вероятности к вероятности безотказной работы:
,
(3.4)
откуда
если λ = const,
(3.5)
Среднее время безотказной работы системы – это математическое ожидание времени работы системы до отказа:
Пределы несобственного интеграла изменяются от 0 до ∞, так как время не может быть отрицательным.
Интегрируем по частям, получим
(3.6)
, так как при верхнем пределе P(t) быстрее стремится к нулю, чем t стремится к бесконечности.
На рис. 3.1 изображена зависимость вероятности безотказной работы от времени. В начальный момент вероятность Р равна единице. В конце времени работы системы Т
вероятность равна нулю.
Показатели надежности функционально связаны между собой: зная одну из функций P(t), Q(t), f(t),
λ(t), можно определить три остальные.
Статистические показатели надежности невосстанавливаемых систем, получаемые из экспериментальных данных, можно определить по следующим формулам:
- статистическая вероятность безотказной работы
,
(3.7)
где N – число объектов в начале испытаний;
ni – число объектов, отказавших за время ti.
Под частотой отказов элементов понимают число отказов в единицу времени, отнесенное к первоначальному количеству поставленных на испытания элементов.
- статистическая частота отказов
,
(3.8)
где ni – число отказов в интервале времени ∆ti;
N – число испытуемых элементов;
∆ti – время испытаний.
При этом отказавшие в процессе испытаний элементы не заменяются новыми, и число работающих
элементов постепенно уменьшается.
В отличие от частоты отказов, интенсивность отказов характеризует надежность объекта в данный
момент времени, т. е. его локальную надежность.
Под интенсивностью отказов понимают число отказов в единицу времени, отнесенное к среднему
числу элементов, безотказно работающих в данный промежуток времени. При этом отказавшие элементы не
заменяются.
- интенсивность отказов:
,
где ni – число отказов за время ∆ti;
(3.9)
– среднее число работоспособных элементов;
Ni – число элементов, работоспособных в начале
рассматриваемого промежутка времени;
Ni+1 – число элементов, работоспособных в конце
промежутка времени ∆ti.
Интенсивность отказов в течение длительной
эксплуатации не остается постоянной. В начальный период времени  имеет большее значение вследствие скрытых дефектов, не обнаруженных из-за несовершенства
производственного контроля и возможных нарушений
правил эксплуатации при первоначальной наладке объекта. Затем значение интенсивности отказов уменьшается и
остается почти постоянным в течение длительного срока.
В конце срока службы λ возрастает из-за старения элементов устройства. На рис. 3.2 изображена зависимость интенсивности отказов от времени.
Среднее время безотказной работы, или средняя наработка на отказ, определится по данным испытаний, как
,
(3.10)
где ti – время исправной работы i-го элемента;
N – общее число испытуемых элементов.
При большом количестве элементов формула (3.10) становится слишком громоздкой. Используется
другой способ вычисления среднего времени
(3.11)
где ni – количество отказавших элементов в интервале времени ∆t = ti+1 - ti;
ti – время в начале i-го интервала;
ti+1 – время в конце i-го интервала;
– среднее время в i-ом интервале;
– число интервалов или разрядов;
tN – время, в течение которого отказали все элементы.
Основные показатели надежности восстанавливаемых (ремонтируемых) систем
Для восстанавливаемых систем характерно чередование времени исправной работы и времени восстановления (ремонтов).
Система, проработав случайное время tp1, выходит из строя. После отказа происходит восстановление, и система работает вновь время tp2 до отказа. Этот процесс продолжается неограниченно. Полагаем, что
время восстановления пренебрежимо мало по сравнению со временем работы. Можно считать, что восстановление происходит мгновенно. Отказавший, испорченный элемент немедленно заменяется новым. Элемент после восстановления имеет такую же надежность, что и в начальный момент.
Пусть интервалы времени безотказной работы между двумя соседними отказами распределены по
экспоненциальному закону. Тогда вероятность того, что за промежуток времени t в системе произойдет n
отказов, определится по формуле Пуассона:
, (n = 0, 1, 2, 3, …),
где λ – среднее число отказов в единицу времени или интенсивность отказов,
λ = const;
λ = Λ, где Λ – параметр потока отказов. Этот параметр определяется по статистической формуле:
,
(3.12)
где N – общее число отказавших элементов, или число восстановлений, остается неизменным. Отказавшие элементы заменяются новыми.
Поток отказов восстанавливаемой системы является простейшим, пуассоновским.
Для ремонтируемых объектов удобным для практики критерием надежности является среднее время
работы между двумя соседними отказами или наработка на отказ Т0.
Значения этого параметра определяются по результатам обработки статистического материала, полученного в ходе эксплуатации или экспериментов.
Если устройство проработало суммарное время t∑ и имело при этом n отказов в работе, то наработка
на отказ
.
(3.13)
Если испытывались N однотипных объектов, то необходимо просуммировать время исправной работы по всем объектам и разделить его на общее число отказов:
.
(3.14)
Для простейшего потока параметр потока отказов определяются по формуле:
.
(3.15)
Восстановление отказавшего элемента часто требует времени, которым нельзя пренебречь. Среднее
время восстановления системы Тв – это математическое ожидание продолжительности восстановления системы после отказа, т. е. среднее время вынужденного, нерегламентированного простоя, вызванного отысканием и устранением отказа.
(3.16)
где Рв – плотность вероятности времени восстановления;
Fв – функция распределения времени восстановления.
Основной характеристикой восстанавливаемой системы является коэффициент готовности. Коэффициент готовности Кг для установившегося режима эксплуатации определяется как вероятность того, что
система
будет
исправна
в произвольно выбранный момент в промежутках между плановыми техническими обслуживаниями
.
(3.17)
Формулы для статистических оценок времени восстановления
и коэффициента готовности
имеют вид:
(3.18)
,
(3.19)
где N – число восстановлений системы;
tВi – время восстановления (ремонта) системы после i-го отказа.
Законы распределения, используемые при оценке надежности
Закон распределения определяется видом аналитических функций, описывающих показатели
надежности: P(t), f(t), λ(t). Закон распределения случайной величины выбирается в зависимости от свойств
объекта, условий его работы, характера отказов.
Согласно распределению Вейбулла, вероятность безотказной работы определяется по формуле
(3.20)
где λ0 и В – параметры.
Частота отказов
(3.21)
Интенсивность отказов
λ = λ0 · B · tB-1.
Среднее время безотказной работы
(3.22)
(3.23)
где
– табулированная гамма-функция.
Закону Вейбулла хорошо подчиняется распределение отказов в объектах, содержащих большое количество однотипных неремонтируемых элементов (полупроводниковых приборов, микромодулей и т. д.).
Особенностью распределения Вейбулла является то, что с изменением параметра В меняется характер зависимости показателя надежности от времени. При В < 1 интенсивность отказов будет монотонно
убывающей функцией, при В > 1 – возрастающей.
Данное свойство позволяет соответствующим подбором параметров λ0 и В обеспечить хорошее совпадение результатов опытных данных с аналитическими выражениями параметров надежности.
Поведение системы на участке приработки хорошо описывается законом распределения Вейбулла с
параметром В < 1, а на участке старения – В > 1.
Экспоненциальное распределение является частным случаем распределения Вейбулла при В = 1.
Интенсивность отказов λ = const.
Вероятность безотказной работы
(3.24)
Наработка на отказ
(3.25)
Экспоненциальное
распределение
хорошо
описывает
поведение
системы
в период нормальной эксплуатации, когда λ = const.
Это распределение не учитывает износа элементов системы.
Экспоненциальное распределение типично для большинства сложных объектов, содержащих большое количество различных неремонтируемых элементов, имеющих преимущественно внезапные отказы изза наличия скрытых дефектов. Данное распределение применяется также к ремонтируемым объектам с простейшим потоком отказов.
Распределение
Релея
достаточно
полно
описывает
и объектов с явно выраженными эффектами износа и старения.
Вероятность безотказной работы при этом распределении
(3.26)
где с – параметр распределения.
Частота отказов
поведение
элементов
(3.27)
Интенсивность отказов
.
(3.28)
Средняя наработка на отказ
(3.29)
Распределение Пуассона применяется для оценки надежности ремонтируемых изделий с простейшим потоком отказов.
(3.30)
где К – число отказов за время t;
λ – интенсивность потока отказов;
PK(t) – вероятность того, что за время t произойдет К отказов.
Нормальное распределение или распределение Гаусса используется для вычисления надежности
объектов, для которых типичен износ. Отказы объектов носят постепенный характер, вследствие старения
элементов.
Плотность вероятности момента отказов
Она зависит от двух параметров: среднего значения времени работы до отказа Т0 и среднеквадратичного отклонения наработки на отказ σ.
Плотность нормального распределения имеет колоколообразную форму, симметричную относительно среднего значения Т0.
Вероятность безотказной работы
(3.31)
где Ф – табулированный интеграл Лапласа.
Интенсивность отказов
(3.32)
Нормальная плотность распределения отлична от нуля при t < 0. Этот недостаток несущественен,
если Т0 >> σ. При этом условии частью кривой распределения при t < 0 можно пренебречь. Если это условие
не выполняется, то использование нормального распределения приводит к погрешностям.
Часть кривой распределения при t < 0 отсекают. Получают усеченное нормальное распределение.
Формулы к усеченному нормальному распределению следующие.
Вероятность безотказной работы:
(3.33)
Интенсивность отказов:
(3.34)
Среднее время безотказной работы:
(3.35)
Интенсивность отказов при нормальном и усеченном нормальном распределениях резко возрастает
с течением времени, что характерно для стареющих устройств.
Аналитические методы расчета надежности информационных систем
Под расчетом надежности понимают определение численных показателей по тем или иным числовым данным.
При аналитическом методе основные показатели надежности: вероятность безотказной работы P(t),
средняя наработка на отказ Т0, определяются по известным интенсивностям отказов элементов, входящих в
данную информационную систему. Элементы информационной системы соединены последовательно, если
отказ любого из элементов приводит к отказу всей системы.
Пусть система состоит из n последовательно соединенных элементов.
Для безотказной работы системы необходимо, чтобы каждый элемент работал безотказно. Так как отказы элементов взаимно независимы, то вероятность безотказной работы системы равна произведению вероятностей элементов.
,
(3.36)
где Р1, Р2, …, Рn – вероятности безотказной работы элементов;
Рi – вероятность безотказной работы i-го элемента;
Рс – вероятность безотказной работы системы.
Пусть функции надежности элементов подчиняются экспоненциальному закону распределения, а
интенсивности отказов не зависят от времени.
где λ1, λ2,…, λn – интенсивности отказов элементов.
Тогда,
(3.37)
Надежность системы также подчиняется экспоненциальному закону распределения.
где λс = λ1 + λ2 + … + λn.
Среднее время безотказной работы системы Т0с = 1/λc.
Вероятность безотказной работы системы при последовательном (основном) соединении элементов
всегда меньше, чем вероятность самого ненадежного элемента. Она существенно возрастает при увеличении
надежности самого ненадежного элемента.
Данные по интенсивностям отказов отдельных элементов радиоэлектронных систем приведены в
табл. 3.3.
Таблица 3.3
Наименование
Интенсив-
Наименование
Интенсив-
элементов
ность отказов
λ·10-6, ч-1
Резисторы
0,01 – 1
Конденсаторы
0,1 – 16
Трансформаторы
0,02 – 6,5
Дроссели, катушки индуктивности
Реле
Интегральные
микросхемы
элементов
ность отказов
λ·10-6, ч-1
Полупроводниковые диоды
Полупроводниковые триоды
Коммутационные
устройства
Штепсельные
разъемы
Соединения пайкой
0,02 – 4,4
0,5 – 100
0,12 – 50
0,01 – 90
0,003 – 3
0,01 – 9
0,1 – 1
0,001 – 0,01
Пусть система состоит из n параллельно соединенных элементов и отказы элементов взаимно независимы. Отказ системы наступает только тогда, когда отказывают все входящие в систему элементы.
Тогда вероятность отказа системы равна произведению вероятностей отказов элементов.
(3.38)
где Qi(t) = 1 – Pi(t) – вероятность отказа i-го элемента в течение времени t.
Безотказная работа системы есть событие, противоположное отказу.
Вероятность безотказной работы системы
Если
интенсивности
и (3.39) принимают вид:
отказов
не
зависят
от
(3.39)
времени,
то
формулы
(3.40)
(3.41)
Если элементы системы имеют одинаковую надежность, т. е.
то вероятность безотказной работы системы
(3.42)
Средняя наработка на отказ системы
Осуществим замену переменных
Получим:
(3.43)
Пусть параллельно включены два элемента с неодинаковыми интенсивностями отказов.
(3.38)
Вероятность безотказной работы системы
Средняя наработка системы до отказа
.
При параллельном включении трех элементов с неодинаковой надежностью:
По
аналогии
запишем
формулу
с неодинаковыми элементами в общем виде:
для
средней
наработки
на
отказ
системы
(3.44)
При увеличении числа параллельно соединенных элементов вероятность безотказной работы системы возрастает.
При смешанном соединении сначала по соответствующим формулам находят надежность цепи из К
последовательно соединенных элементов, затем надежность системы из m параллельных ветвей.
При определении вероятности безотказной работы системы с произвольным соединением элементов
используется метод минимальных путей.
Минимальный путь – это такой минимальный набор работоспособных элементов, исключение любого из которых (т. е. отказ) переводит систему из состояния работоспособности в состояние отказа. У системы с произвольной структурой может быть несколько минимальных путей. Последовательное соединение из n элементов имеет один минимальный путь. Параллельное соединение из n элементов имеет n минимальных путей, проходящих через каждый элемент.
Повышение надежности систем путем резервирования
В природе нет абсолютно надежных элементов и изделий. Каждый элемент, как бы совершенен он
ни был, со временем теряет свои свойства. Получение элементов сверхвысокой надежности либо вообще
недоступно существующему уровню техники, либо требует таких больших расходов, что они уже не могут
быть оправданы. Приходится для повышения надежности изделия идти другими путями. Один из самых
распространенных путей повышения надежности – путь резервирования. Резервирование – это способ повышения надежности, состоящий в том, что в систему вводятся избыточные элементы, узлы, агрегаты, которые включаются в работу по мере выхода из рабочего состояния основных элементов, узлов, агрегатов.
Резервирование приводит к увеличению массы, габаритов, стоимости аппаратуры.
Присоединение резервированных элементов к основным выполняется параллельно.
Различают три метода резервирования.
1. Общее, предусматривающее резервирование объекта в целом. На рис. 3.6 изображена схема общего резервирования.
2. Раздельное, предусматривающее резервирование отдельных элементов, их групп или отдельных
узлов. На рис. 3.7 показана схема раздельного резервирования.
1
Рис. 3.7
3. Смешанное, предусматривающее совмещение различных методов резервирования.
Различают однократное (дублирование) и многократное резервирование.
Резервирование может быть с ремонтом любого основного или резервного элемента в процессе эксплуатации,
т. е.
резервирование
с
восстановлением
и без ремонта элементов, т. е. резервирование без восстановления.
Вероятность безотказной работы системы с общим резервированием
где m – число резервных цепей;
Pi – вероятность безотказной работы i-й цепи.
где Pji – вероятность безотказной работы j-го элемента в i-й цепи;
n – число последовательно соединенных элементов цепи.
(3.45)
При экспоненциальном законе распределения надежности и одинаковых элементах, когда
(3.46)
Среднее время безотказной работы при общем резервировании и одинаковой надежности параллельно включенных цепей:
(3.47)
В случае раздельного поэлементного резервирования эквивалентная вероятность безотказной работы группы параллельно соединенных элементов имеет вид:
где Рij – надежность i-го элемента в j-й цепи.
Вероятность безотказной работы системы равна произведению вероятностей последовательно соединенных эквивалентных элементов
(3.48)
Если надежность всех элементов одинакова и подчиняется экспоненциальному закону распределения, то
(3.49)
Среднее время безотказной работы при раздельном резервировании и одинаковых элементах в системе
(3.50)
где
По заданной вероятности безотказной работы (ВБР) системы можно определить требуемую вероятность отдельного элемента.
Сравним эффективность общего и раздельного (поэлементного) резервирования.
Резервированная система состоит из одинаковых элементов.
Если ВБР системы равна Pc(t), то ВБР отдельного элемента находится из формулы
(3.51)
где d – число последовательных групп элементов в системе;
n – количество последовательных элементов в группе;
m – число комплектов каждой группы.
При общем резервировании (d = 1)
(3.52)
При раздельном резервировании (d = n):
(3.53)
Если резервирование должно обеспечить заданную ВБР системы, то необходимое количество комплектов оборудования m при числе резервируемых групп, равных d должно быть равно:
(3.54)
При раздельном резервировании d = n, тогда
(3.55)
При общем резервировании (d = 1):
(3.56)
Существуют четыре способа включения резерва: постоянное, замещением,
скользящее и облегченное.
Постоянным или нагруженным резервированием называется такое, при котором резервные элементы участвуют в функционировании объекта, наряду с основными.
Резервирование, при котором функции основного элемента передаются резервному только после отказа основного элемента, называется резервированием замещением или ненагруженным резервом.
Система с ненагруженным резервом представляет собой систему с параллельным соединением элементов, в котором, в каждый момент времени, работает
только один элемент. Если работающий элемент выходит из строя, то включается другой элемент. На рис.
3.9 показана структура системы с ненагруженным резервом или с резервированием замещением.
Резервные элементы обозначаются 1, 2, …, m в порядке их включения. Полагают, что переключатель является безотказным. Все элементы имеют одинаковые интенсивности отказов λ.
Возможны два события, соответствующие безотказной работе двухэлементной системы с резервированием замещением до момента времени t:
1) основной элемент работает время t;
2) основной элемент отказывает в момент τ < t, включается и продолжает работать резервный элемент.
Эти события являются непересекающимися, образуют простейший поток.
Вероятность безотказной работы системы равна сумме вероятностей данных событий и определяется по формуле Пуассона:
где К – число отказов за время t.
В случае трехэлементной системы
По аналогии запишем выражение вероятности безотказной работы системы с ненагруженным резервом в общем случае
(3.57)
Работа системы с резервированием замещением заканчивается, когда число отказавших элементов
становится равным m + 1.
Среднее время безотказной работы системы То замещ определяется по формуле
(3.58)
где To – среднее время безотказной работы основного элемента.
Резервирование замещением, при котором группа основных элементов объекта резервируется одним или несколькими резервными элементами, каждый из которых может заменить любой отказавший основной элемент в данной группе, называют скользящим резервированием. Скользящее резервирование применяют при наличии в аппаратуре одинаковых элементов, узлов, блоков. Вероятность безотказной работы и
средняя наработка на отказ при скользящем резервировании вычисляются по формулам (3.57), (3.58).
Ненагруженный резерв, в любом случае, более эффективен, чем нагруженный, так как резервные
элементы не работают до выхода из строя основного элемента.
От момента включения элемента до момента, когда он становится работоспособным, проходит некоторое время, пока элемент разогревается. Если же условия эксплуатации не допускают перерыва в работе
данной системы, применяют облегченный или недогруженный резерв. Сущность этого режима заключается
в том, что резервный элемент, до момента включения в работу, находится в облегченном режиме, а после
включения начинает работать в нормальном рабочем режиме. Элемент может отказать, находясь в нерабочем состоянии, но с меньшей вероятностью.
При недогруженном состоянии резерва вероятность безотказной работы системы Робл определяется
как:
(3.59)
Средняя наработка на отказ
(3.60)
где λ0 – интенсивность отказа основного элемента;
λИ – интенсивность отказа резервного устройства до замещения;
(3.61)
Расчет надежности по статистическим данным
Для оценки надежности по статистическим данным необходима большая работа по правильному и
объективному сбору этих данных.
Расчет надежности может проводиться либо в процессе испытаний на надежность, либо на основе
опыта эксплуатации.
Особенностью оценки надежности по статистическим данным является ограниченность статистического материала, которого недостаточно для точного определения показателей надежности. Приближенное
случайное значение показателя называется оценкой показателя.
К оценке ā показателя а предъявляется ряд требований, которым она должна удовлетворять.
Оценка ā должна при увеличении числа опытов приближаться к показателю а. Оценка, обладающая
таким свойством, называется состоятельной.
Оценка ā не должна иметь систематической ошибки. (Систематической ошибкой называют неслучайную ошибку, искажающую результаты измерений в одну определенную сторону).
Например, часы спешат на несколько минут. Измерение времени этими часами систематически (постоянно) дает завышенные результаты.
Математическое ожидание оценки должно быть равно истинному значению параметра а. М[ā] = a.
Оценка, удовлетворяющая этому свойству, называется несмещенной.
Выбранная несмещенная оценка должна, по сравнению с другими, иметь наименьшую дисперсию.
Оценка, обладающая такими свойствами, называется эффективной.
Точечной называется оценка, определяемая одним числом. Точечные оценки вычисляются по формулам:
или
где n – число опытов.
При малом числе опытов точечная оценка может значительно отличаться от оцениваемого параметра, приводить к грубым ошибкам.
При небольшом объеме опытов следует пользоваться интервальными оценками. Интервальной
называют оценку, которая определяется двумя числами, концами интервала.
Доверительным называют интервал
, который накрывает неизвестный параметр
с заданной вероятностью ;  – ошибка при замене параметра
оценкой .
Доверительной вероятностью называют вероятность того, что некоторый интервал возможных значений
(доверительный интервал) накроет истинное значение величины
границы интервала
Доверительные границы – это
,
Доверительные интервалы при нормальном распределении случайной величины
Пусть случайная величина Х распределена по нормальному закону (закону Гаусса) с математическим ожиданием M и среднеквадратичным отклонением . Математическое ожидание M является истинным
значением случайной величины Х.
Определим вероятность неравенства.
(3.62)
где
– оценка математического ожидания;
– доверительная вероятность;
– ошибка от замены M оценкой
Параметры распределения случайной величины
(3.62) невозможно.
Поделим обе части неравенства
где
деляемое из опытных данных;
и
на
неизвестны, поэтому решить уравнение
,
– исправленное среднеквадратическое отклонение, опре-
– статистическая дисперсия;
n – число опытов.
Получим:
(3.63)
или
Случайная величина Т подчиняется распределению Стьюдента.
Дифференциальная функция распределения имеет вид:
где
– гамма-функция
Распределение Стьюдента зависит от числа опытов или, что то же самое, от числа степеней свободы
Распределение Стьюдента позволяет найти решение уравнения (3.62).
Величина
Функция
, называемая квантилем распределения Стьюдента, определится из условия
– четная, поэтому
Квантилем, отвечающим заданному уровню вероятности , называют такое значение
, при
котором функция принимает значение, равное , т. е.
Квантиль t находим из таблицы распределения Стьюдента, в зависимости от доверительной вероятности и числа степеней свободы
.
Величина , равная половине длины доверительного интервала, определится по формуле
Доверительные интервалы для оценок параметров рассчитываются следующим образом.
1. Задаются доверительной вероятностью
2. Определяется число степеней свободы
. Обычно  = 0,8; 0,9; 0,95; 0,99.
, где n – число опытов или наблюдений.
3. Из таблицы распределения Стьюдента по заданным r и  находят квантиль
.
4. Из опытных данных определяется исправленное среднеквадратическое отклонение:
где
5. Половина длины доверительного интервала определяется по формуле:
6. Доверительный интервал будет:
Доверительные интервалы при экспоненциальном распределении случайной величины
Для определения доверительного интервала случайной величины, распределенной по симметричному закону, близкому к нормальному, используется распределение Стьюдента. При несимметричном законе применяют распределение Пирсона или распределение 2.
Дифференциальная функция распределения 2 имеет вид:
Распределение 2 зависит от одного параметра r, называемого числом степеней свободы.
Составлены специальные таблицы распределения 2, пользуясь которыми, можно по заданной дои числу степеней свободы r найти значение квантиля распределения 2.
верительной вероятности
При экспоненциальном законе распределения отказов оценки параметров
,
,
(3.64)
где n – число отказов в интервале времени
– суммарная наработка.
Для неремонтируемых элементов (объектов)
(3.65)
где
– время исправной работы i-го отказавшего элемента (объекта);
N – количество объектов;
– время испытаний;
n – число отказавших объектов.
В случае, когда испытания проводятся до тех пор, пока не откажут все выставленные на испытания
объекты, суммарная наработка
(3.66)
Для ремонтируемых объектов
(3.67)
где
– длительность испытаний.
Доверительный интервал для интенсивности отказов, в этом случае, находится с помощью таблицы
c2, в которой параметрами являются доверительная вероятность
Нижняя
и верхняя
границы интенсивностей отказов:
, где
(3.68)
, где
В формулах:
,
и число степеней свободы r.
(3.69)
– квантили распределения
при числе степеней свободы
– коэффициенты.
Определение доверительных интервалов при отсутствии отказов
Пусть производятся испытания какого-либо изделия на безотказность работы. Вероятность отказа
очень мала. В результате испытаний изделие не отказало ни разу. Найти максимальную, практически возможную, вероятность отказа.
Поставим эту задачу в общем виде. Произведено n независимых опытов, ни в одном из которых событие А не произошло. Задана доверительная вероятность , требуется построить доверительный интервал
для вероятности Р события А, точнее найти его верхнюю границу Р2, так как нижняя граница Р1 равна нулю.
В результате n опытов наблюдается противоположное событие В, состоящее в том, что событие А не
появилось ни разу. Вероятность этого события определяется по формуле Бернулли при m = 0, где m – число
появлений события В.
,
Получим уравнение для вероятности P2:
откуда
.
(3.70)
Обратная задача.
Событие А с малой вероятностью ни разу не наблюдалось в серии из n опытов. Задана доверительная вероятность . Каково должно быть число опытов, чтобы верхняя доверительная граница для вероятности события была равна заданному значению Р2.
Из формулы (3.70) получим
(3.71)
Критерии согласия. Критерий Пирсона
Критерием согласия называется критерий проверки гипотезы о том, что статистическое распределение согласуется с каким-либо известным законом (нормальным, экспоненциальным, Вейбулла и т. д.)
Имеется несколько критериев согласия: Колмогорова, Пирсона и т. д.
Критерий Пирсона не требует построения самого закона распределения. Достаточно задаться только
общим видом функции F(t), а входящие в нее числовые параметры определяются по данным эксперимента.
Предположим, что произведено n независимых опытов, в каждом из которых случайная величина
принимает определенное значение. Результаты опытов оформлены в виде статистического ряда с числом
разрядов К.
…
…
…
n – общее число значений случайной величины;
ni – число значений в i-ом разряде;
– статистическая вероятность i-ом разряде.
Требуется проверить, согласуются ли экспериментальные данные с гипотезой, что случайная величина Х имеет данный закон распределения. Этот закон распределения называется теоретическим. Из теоретического закона определяются теоретические вероятности попадания случайной величины в каждый разряд:
Сущность критерия согласия Пирсона состоит в сравнении теоретических и статистических вероятностей.
В качестве критерия проверки гипотезы принимают случайную величину
(3.72)
Эта величина при
стремится к закону распределения
степеней свободы находят по равенству
с r степенями свободы. Число
,
(3.73)
где k – число интервалов;
s – число параметров предполагаемого распределения, которые вычислены по экспериментальным
данным.
Если предполагаемое распределение нормальное, то оценивают два параметра: математическое
ожидание
и
среднеквадратичное
отклонение.
Поэтому
s = 2 и число степеней свободы
Если статистические данные распределены по экспоненциальному закону, то оценивают параметр
, поэтому s = 1 и
Пользуясь таблицами распределения
можно для вычисленной по формуле (3.72) меры расхождения и числа степеней свободы r найти вероятность P того, что величина, распределенная по закону
превзойдет эту меру. Если эта вероятность мала, меньше или равна 0,1, событие с такой вероятностью
можно считать практически невозможным.
Гипотезу о том, что закон распределения X есть F(x) следует считать неправдоподобной. Если же
вероятность Р больше 0,1, гипотезу о том, что величина X распределена по закону F(x) следует считать
правдоподобной, не противоречащей опытным данным.
Последовательность операций при использовании критерия Пирсона.
1. Определяется мера расхождения опытного и теоретического закона
где ni – количество значений случайной величины в i-ом интервале;
n – общее число значений случайной величины;
– частота повторения событий или статистическая вероятность в i-ом интервале.
– теоретическая вероятность события в i-ом интервале (из теоретической кривой);
k – число разрядов (интервалов);
– наблюдаемое значение критерия.
2. Определяется число степеней свободы распределения
по формуле
.
3. Пользуясь таблицами распределения
, возможно для значения
, вычисленного в пункте
1 и числа степеней свободы r определить вероятность Р. Если эта вероятность мала (Р  0,1), гипотеза о совпадении опытного и теоретического законов отбрасывается. Если Р > 0,1, гипотезу можно принять не противоречащей опытным данным.
Критерий Колмогорова
При применении критерия согласия Колмогорова в качестве меры расхождения между теоретическим и статистическим распределением рассматривается максимальное значение модуля разности между
теоретической и экспериментальной функциями распределения.
На
основе
этого
критерия,
экспериментальное
распределение
согласуется
с выбранным теоретическим, если выполняется условие
где
– наибольшее отклонение теоретической кривой распределения
от экспериментальной;
n – общее количество экспериментальных данных.
Критерий Колмогорова прост и нагляден.
Недостатком критерия является то, что он требует предварительного знания теоретического распределения, т. е. знания не только вида функции распределения F(t), но и ее параметров.
ПОВЫШЕНИЕ НАДЕЖНОСТИ ИНФОРМАЦИОННЫХ СИСТЕМ С ПОМОЩЬЮ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ
Принципы помехоустойчивого кодирования
В реальных условиях приём двоичных символов происходит с ошибками, т. е. вместо символа «1»
принимается символ «0», и наоборот. Ошибки могут возникать из-за помех, действующих в канале связи
(особенно помех импульсного характера), изменения за время передачи характеристик канала (например,
замирания), снижения уровня передачи, нестабильности амплитудных и фазочастотных характеристик канала и т. п.
Общепринятым критерием оценки качества передачи в дискретных каналах является нормированная на знак или символ допустимая вероятность ошибки для данного вида сообщений. Так, допустимая вероятность ошибки при телеграфной связи может составлять 10 -3 (на знак), а при передаче данных – не более
10-6 (на символ). Для обеспечения таких значений вероятностей одного улучшения только качественных
показателей канала связи может оказаться недостаточным. Поэтому основной мерой является применение
специальных методов повышения качества приёма передаваемой информации [12]. Эти методы можно разбить на две группы.
К первой группе относятся методы увеличения помехоустойчивости приёма единичных элементов
(символов) дискретной информации, связанные с выбором уровня сигнала, отношения сигнал-помеха (энергетические характеристики), ширины полосы канала, методов приёма и т. д.
Ко второй группе относятся методы обнаружения и исправления ошибок, основанные на искусственном введении избыточности в передаваемое сообщение. Увеличить избыточность передаваемого сигнала можно различными способами. Так как объём сигнала
,
(4.1)
где Р – мощность сигнала, Вт; ∆F – ширина спектра сигнала, Гц; Т – время передачи сигнала, с, то
его увеличение возможно за счёт увеличения Р, ∆F и Т.
Практические
возможности
увеличения
избыточности
за
счёт
мощности
и ширины спектра сигнала в системах передачи дискретной информации по стандартным каналам резко
ограничены. Поэтому для повышения качества приёма, как правило, идут по пути увеличения времени передачи и используют следующие основные способы:
1) многократная передача кодовых комбинаций (метод повторения);
2) одновременная передача кодовой комбинации по нескольким параллельно работающим каналам;
3) помехоустойчивое (корректирующее) кодирование, т. е. использование кодов, исправляющих
ошибки.
Иногда применяют комбинации этих способов.
Многократное повторение (e раз) кодовой комбинации является самым простым способом повышения достоверности приёма и легко реализуется, особенно в низкocкopocтных cистeмax пepeдaчи для каналов
с быстроменяющимися параметрами.
Способу
многократного
повторения
аналогичен
способ
передачи
одной
и той же информации по нескольким параллельным каналам связи. В этом случае необходимо иметь не менее трёх каналов связи (например, с частотным разнесением), несущие частоты которых нужно выбирать
таким образом, чтобы ошибки в каналах были независимы. Достоинством таких систем являются надёжность и малое время задержки в получении информации. Основным недостатком многоканальных систем
так же, как и систем с повторением, является нерациональное использование избыточности.
Наиболее целесообразно избыточность используется при применении помехоустойчивых (корректирующих) кодов.
При помехоустойчивом кодировании чаще всего считают, что избыточность источника сообщений
на входе кодера равна 0 (χ = 0). Это обусловлено тем, что очень многие дискретные источники (например,
цифровая информация на выходе ЭВМ) обладают малой избыточностью. Если избыточность первичных
источников сообщений существенна, то в этих случаях, по возможности, стремятся ее уменьшить путём эффективного кодирования, применяя, например, коды Шеннона – Фано или Хафмена. Затем, методами помёхоустойчивого кодирования можно внести такую избыточность в сигнал, которая позволит достаточно простыми средствами улучшить качество приёма. Таким образом, эффективное кодирование вполне может сочетаться с помехоустойчивым.
В обычном равномерном помехоустойчивом коде число разрядов n в кодовых комбинациях определяется числом сообщений и основанием кода.
Коды, у которых все кодовые комбинации разрешены к передаче, называются простыми или равнодоступными и являются полностью безызбыточными. Безызбыточные первичные коды обладают большой
«чувствительностью» к помехам.
Внесение избыточности при использовании помехоустойчивых кодов обязательно связано с увеличением n – числа разрядов (длины) кодовой комбинации. Таким образом, всё множество N = 2∙n комбинаций
можно разбить на два подмножества: подмножество разрешённых комбинаций, т. е. обладающих определёнными признаками, и подмножество запрещённых комбинаций, этими признаками не обладающих.
Помехоустойчивый код отличается от обычного тем, что в канал передаются не все кодовые комбинации N, которые можно сформировать из имеющегося числа разрядов n, а только их часть Nk, которая составляет подмножество разрешённых комбинаций.
Если при приёме выясняется, что кодовая комбинация принадлежит к запрещённым, то это свидетельствует о наличии ошибок в комбинации, т. е. таким образом решается задача обнаружения ошибок. При
этом принятая комбинация не декодируется (не принимается решение о переданном сообщении).
В связи с этим помехоустойчивые коды называют корректирующими кодами. Корректирующие свойства
избыточных кодов зависят от правила их построения, определяющего структуру кода, и параметров кода
(длительности символов, числа разрядов, избыточности и т. п.).
Первые работы по корректирующим кодам принадлежат Хеммингу, который ввёл понятие минимального кодового расстояния dmin и предложил код, позволяющий однозначно указать ту позицию в кодовой комбинации, где произошла ошибка. К k информационным элементам в коде Хемминга добавляется r
проверочных элементов для автоматического определения местоположения ошибочного символа. Коды Хемминга будут рассмотрены подробнее далее.
Классификация помехоустойчивых кодов
На рис. 4.1 приведена упрощённая классификация помехоустойчивых кодов [17]. Остановимся
кратко на основных особенностях различных классов кодов. Помехоустойчивые (корректирующие) коды
делятся на блочные и непрерывные.
Рис. 4.1
Блочными называются коды, в которых информационный поток символов разбивается на отрезки и
каждый из них преобразуется в определённую последовательность (блок) кодовых символов. В блочных
кодах кодирование при передаче (формирование проверочных элементов) и декодирование при приёме (обнаружение и исправление ошибок) выполняются в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам. Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью элементов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными цепными.
В простейшем цепном коде каждый проверочный элемент формируется путём сложения по модулю
2 соседних или отстоящих друг от друга на определённое число позиций информационных элементов. В
канал связи передаётся последовательность импульсов, в которой за каждым информационным следует проверочный. Подобную чередующуюся последовательность разрядов имеет, например, корреляционный манчестерский код.
К непрерывным кодам относятся и свёрточные коды, в которых каждый информационный символ,
поступающий на вход кодирующего устройства, вызывает появление на его выходе ряда проверочных элементов, образованных суммированием по модулю 2 данного символа и k-1 предыдущих информационных
символов. Рекуррентные коды позволяют исправлять групповые ошибки («пачки») в каналах связи.
Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число n-символов (разрядов) с постоянной
длительностью τ0 импульсов символов кода. Равномерные коды, в основном, и применяются в системах связи, так как это упрощает технику передачи и приёма.
Классическими примерами неравномерного кода являются: код Морзе, широко применяемый в телеграфии, и код Хафмена, применяемый для компрессии информации (факсимильная связь, ЭВМ).
Никаких специальных мер по исправлению и обнаружению ошибок в коде Морзе не предусматривается в связи с большой избыточностью самого передаваемого текста. В этом смысле, код Морзе не относится к классу корректирующих кодов.
Почти все блочные корректирующие коды принадлежат к разделимым кодам, в которых кодовые
комбинации состоят из двух частей: информационной и проверочной. Их символы всегда занимают одни и
те же позиции, т. е. располагаются на определенных местах. Как правило, в таких кодах, все кодовые комбинации которых содержат n символов, первые k символов являются информационными, а за ними располагаются (n-k) проверочных символов. В соответствии с этим разделимые коды получили условное обозначение – (n-k)-коды.
В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким
кодам относятся, в частности, коды с постоянным весом, так называемые равновесные коды. Например,
Международным консультативным комитетом по телеграфии и телефонам (МККТТ) рекомендован для использования телеграфный код № 3 – семиразрядный код с постоянным весом, т. е. с числом единиц в каждой кодовой комбинации, равным 3 (W = 3).
Систематические коды образуют наиболее обширную группу (n, k)-разделимых кодов. Особенностью этих кодов является то, что проверочные (корректирующие) символы образуются с помощью линейных операций над информационными. Кроме того, любая разрешённая кодовая комбинация может быть
получена в результате линейной операции над набором k линейно независимых кодовых комбинаций. В
частности, суммирование по модулю 2 двух и более разрешённых комбинаций также дает разрешённую кодовую комбинацию. Поскольку теоретической основой получения таких комбинаций является математический
аппарат
линейной
алгебры,
то
коды
и
называют
линейными,
а учитывая, что проверочные символы формируются по определённой системе (правилам), блочные равномерные разделимые линейные коды получили название систематических. Использование аппарата линейной
алгебры, в которой важное значение имеет понятие «группа», породило и другое название этих кодов –
групповые.
Эти коды получили наибольшее применение в системах передачи дискретной информации.
Несистематические (нелинейные) коды указанными выше свойствами не обладают и применяются
значительно реже, в специальных случаях. Примером нелинейного кода является уже упоминавшийся
неразделимый, равновесный код. Эти коды обычно используются в несимметричных каналах связи, в которых вероятность перехода 1 в 0 значительно больше вероятности перехода 0 в 1, или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке были переходы обоих видов, и поэтому почти все ошибки
приводят к изменению веса блока и, следовательно, обнаруживаются.
Другим примером несистематического кода является код с контрольным суммированием – итеративный код. В этом коде проверочные разряды формируются в результате суммирования значений разрядов,
как в данной кодовой комбинации, так и одноимённых разрядов в ряде соседних с ней комбинаций, образующих совместный блок. Итеративные коды позволяют получить так называемые мощные коды, т. е. коды с
длинными блоками и большим кодовым расстоянием при сравнительно простой процедуре декодирования.
Итеративные коды могут строиться как комбинационные, посредством произведения двух или более систематических кодов.
К комбинационным кодам можно отнести также антифединговые коды, предназначенные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таких каналов с группированием ошибок применяют метод перемежения символов или декорреляции ошибок. Он заключается в
том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а
перемежаются символами других кодовых комбинаций исходного систематического или любого другого
кода. Если интервал между символами, входящими в одну кодовую комбинацию, сделать длиннее «памяти»
(интервала корреляции) канала с замираниями, то в пределах длительности одной исходной кодовой комбинации группирования ошибок не будет. На приёме после обратной «расфасовки» в кодовых комбинациях
можно производить декодирование с обнаружением и исправлением ошибок.
В систематических кодах различают два метода формирования проверочной группы символов: поэлементный и в целом.
Наиболее известны среди систематических кодов коды Хемминга, которые исторически были
найдены раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов.
В этих кодах используется принцип проверки на чётность определённого ряда информационных символов.
Проверочная группа из r символов формируется поэлементно по соответствующему алгоритму. Коды Хемминга, имеющие dmin = 3, позволяют исправить одну ошибку.
Расширенные
коды
Хемминга
строятся
в
результате
дополнения
кодов
с dmin = 3 общей проверкой каждой из кодовых комбинаций на чётность, т. е. ещё одним проверочным символом. Это позволяет увеличить минимальное кодовое расстояние до dmin = 4.
Циклические коды также относятся к классу линейных систематических кодов и обладают всеми их
свойствами. Коды названы циклическими потому, что циклический сдвиг любой разрешённой кодовой комбинации также является разрешённой комбинацией. Теория построения циклических кодов базируется на
разделах высшей алгебры, изучающей свойства двоичных многочленов. Особую роль в этой теории играют
так называемые неприводимые многочлены, т. е. полиномы, которые не могут быть представлены в виде
произведения многочленов низших степеней. В связи с этим, циклические коды относят к разновидности
полиномиальных кодов.
Среди циклических кодов особое место занимает класс кодов, предложенных Боузом и РойЧоудхури и независимо от них – Хоквингемом. Коды Боуза – Чоудхури – Хоквингема, БЧХ-коды отличаются специальным выбором порождающего (образующего) циклический код полинома, что приводит к простой процедуре декодирования.
В циклических кодах r проверочных символов, добавляемых к исходным k информационным, могут
быть получены сразу, т. е. в целом, в результате умножения исходной подлежащей передаче кодовой комбинации Q(x) простого кода на одночлен xr и добавлением к этому произведению остатка R(x), полученного
в результате деления произведения на порождающий полином Р(х).
Отметим, что коды Хемминга также можно получить по алгоритмам формирования циклических
кодов.
Проблема помехоустойчивого кодирования представляет собой обширную область теоретических и
прикладных исследований. Основными задачами при этом являются следующие: отыскание кодов, эффективно исправляющих ошибки требуемого вида; нахождение методов кодирования и декодирования
и простых способов их реализации.
Наиболее разработаны эти задачи применительно к систематическим кодам. Такие коды успешно
применяются в вычислительной технике, различных автоматизированных цифровых устройствах и цифровых системах передачи информации.
Основные характеристики корректирующих кодов
В настоящее время наибольшее внимание, с точки зрения технических приложений, уделяется двоичным блочным корректирующим кодам. При использовании блочных кодов цифровая информация передаётся в виде отдельных кодовых комбинаций (блоков) равной длины. Кодирование и декодирование каждого
блока осуществляется независимо друг от друга.
Почти все блочные коды относятся к разделимым кодам, кодовые комбинации которых состоят из
двух частей: информационной и проверочной. При общем числе n символов в блоке число информационных
символов равно k, а число проверочных символов
r = n - k.
(4.2)
К основным характеристикам корректирующих кодов относятся:
- число разрешённых и запрещённых кодовых комбинаций (N0, Nk);
- избыточность кода (χ);
- минимальное кодовое расстояние (dmin);
- число обнаруживаемых или исправляемых ошибок (g0);
- корректирующие возможности кодов.
Для блочных двоичных кодов, с числом символов в блоках равным n, общее число возможных кодовых комбинаций определяется выражением
N0 = 2n.
(4.3)
Число разрешённых кодовых комбинаций при наличии k информационных разрядов в первичном
коде равно
Nk = 2k.
(4.4)
Очевидно, что число запрещённых комбинаций равно:
Nз = N0 – Nk = 2n - 2k,
(4.5)
а с учётом (4.2) отношение будет:
N0 /Nk = 2n /2k = 2n-k = 2r,
(4.6)
где r – число избыточных (проверочных) разрядов в блочном коде.
Избыточностью корректирующего кода называют величину
χ = r/n = (n-k)/n = 1 – k/n = 1 – log2 Nk / log2 N0,
(4.7)
откуда следует
Bk = k/n = 1 – χ.
(4.8)
Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют
информационные символы. В теории кодирования величину Bk называют относительной скоростью кода.
Если производительность источника информации равна Н символов в секунду, то скорость передачи после
кодирования этой информации окажется равной
B = H∙(k/n),
(4.9)
поскольку в закодированной последовательности из каждых n символов только k символов являются информационными.
Если число ошибок, которые нужно обнаружить или исправить, значительно, то необходимо иметь
код с большим числом проверочных символов. Чтобы при этом скорость передачи оставалась достаточно
высокой, необходимо в каждом кодовом блоке одновременно увеличивать как общее число символов, так и
число информационных символов. При этом длительность кодовых блоков будет существенно возрастать,
что приведёт к задержке информации при передаче и приёме. Чем сложнее кодирование, тем длительнее
временная задержка информации.
Для того, чтобы можно было обнаружить и исправить ошибки, разрешённая комбинация должна как
можно больше отличаться от запрещённой. Если ошибки в канале связи действуют независимо, то вероятность преобразования одной кодовой комбинации в другую будет тем меньше, чем большим числом символов они различаются.
Если интерпретировать кодовые комбинации как точки в пространстве, то отличие выражается в
близости этих точек, т. е. в расстоянии между ними.
Количество разрядов (символов), которыми отличаются две кодовые комбинации, можно принять за
кодовое расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации по модулю 2 и подсчитать число единиц в полученной сумме. Например, две кодовые комбинации xi =
01011 и xj = 10010 имеют расстояние d(xi, xj), равное 3, так как
xi = 01011 имеет W = 3, xj = 10010 имеет W = 2.
Заметим, что кодовое расстояние d(xj, x0) между комбинацией xj и нулевой (х0 = 00…0) называют весом W комбинации xi, т. е. вес xi равен числу «1» в ней.
xi
xj = 11001 → d(xj, xj) = 3.
(4.10)
Под операцией « » понимается сложение по модулю 2).
Расстояние между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, в безызбыточном первичном натуральном коде (n = k) это расстояние для различных комбинаций может изменяться от единицы до величины n, равной значности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное кодовое расстояние dmin, определяемое при попарном сравнении всех кодовых комбинаций, которое называют расстоянием Хемминга.
В безызбыточном коде все комбинации являются разрешёнными, и, следовательно, его минимальное кодовое расстояние равно единице – dmin = 1. Поэтому достаточно исказиться одному символу, чтобы
вместо переданной комбинации была принята другая разрешённая комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешёнными комбинациями не менее двух – dmin ≥ 2.
Минимальное кодовое расстояние является важнейшей характеристикой помехоустойчивых кодов,
указывающей на гарантируемое число обнаруживаемых или исправляемых заданным кодом ошибок.
При применении двоичных кодов учитывают только дискретные искажения, при которых единица
переходит в нуль (1 → 0) или нуль переходит в единицу (0 → 1). Переход 1→ 0 или 0 → 1 только в одном
элементе кодовой комбинации называют единичной ошибкой (единичным искажением). В общем случае,
под кратностью ошибки подразумевают число позиций кодовой комбинации, на которых под действием
помехи одни символы оказались заменёнными на другие. Возможны двукратные (g = 2) и многократные (g
> 2) искажения элементов в кодовой комбинации в пределах 0 ≤ g ≤ n.
Минимальное кодовое расстояние является основным параметром, характеризующим корректирующие способности данного кода. Если код используется только для обнаружения ошибок кратностью g0, то
необходимо и достаточно, чтобы минимальное кодовое расстояние было равно
dmln ≥ g0 + 1.
(4.11)
В этом случае никакая комбинация из g0 ошибок не может перевести одну разрешённую кодовую
комбинацию в другую разрешённую. Таким образом, условие обнаружения всех ошибок кратностью g0
можно записать в виде:
g0 ≤ dmin – 1.
(4.12)
Чтобы можно было исправить все ошибки кратностью gi и менее, необходимо иметь минимальное
расстояние, удовлетворяющее условию:
dmin ≥ 2 ∙ gu + 1.
(4.13)
В этом случае любая кодовая комбинация с числом ошибок gu отличается от каждой разрешённой
комбинации не менее чем в gu + 1 позициях. Если условие (4.13) не выполнено, возможен случай, когда
ошибки кратности g исказят переданную комбинацию так, что она станет ближе к одной из разрешённых
комбинаций, чем к переданной или даже перейдёт в другую разрешённую комбинацию. В соответствии с
этим, условие исправления всех ошибок кратностью не более gu можно записать в виде:
gu ≤ (dmin – 1)/2.
(4.14)
Из (4.11) и (4.13) следует, что если код исправляет все ошибки кратностью gu, то число ошибок,
которые он может обнаружить, равно g0 = 2 ∙ gu. Следует отметить, что соотношения (4.11) и (4.13) устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при заданном dmin и не ограничивают возможность обнаружения ошибок большей кратности. Например, простейший
код с проверкой на чётность с dmin = 2 позволяет обнаруживать не только одиночные ошибки, но и любое
нечётное число ошибок в пределах g0  n.
При независимых ошибках полная вероятность ошибки кратности g, учитывающая все сочетания
ошибочных символов определяется выражением [8]:
,
где
(4.15)
;
– вероятность искажения одного символа.
Отсюда вероятность отсутствия ошибок в кодовой комбинации, т. е. вероятность правильного приема равна
(4.16)
и вероятность правильного корректирования ошибок равна
.
(4.17)
Здесь суммирование производится по всем значениям кратности ошибок g, которые обнаруживаются и исправляются. Таким образом, вероятность некорректируемых ошибок будет равна
.
(4.18)
Анализ формулы (4.18) показывает, что при малой величине P0 и небольших значениях n, наиболее
вероятны ошибки малой кратности, которые необходимо корректировать в первую очередь.
Вопрос о минимально необходимой избыточности, при которой код обладает нужными корректирующими свойствами, является одним из важнейших в теории кодирования. Этот вопрос до сих пор не получил полного решения. В настоящее время получен лишь ряд верхних и нижних оценок (границ), которые
устанавливают связь между максимально возможным минимальным расстоянием корректирующего кода и
его избыточностью.
Так, граница Плоткина даёт верхнюю границу кодового расстояния dmin при заданном числе разрядов n в кодовой комбинации и числе информационных разрядов k, и для двоичных кодов:
dmin ≤ (n ∙2 ∙ k – 1 ) ∕ (2 ∙ k -1)
(4.19)
или
r ≥ 2 ∙ (dmin - 1) – log2 dmin,
(4.20)
при n ≥ 2 ∙ dmin – 1.
Верхняя граница Хемминга устанавливает максимально возможное число разрешённых кодовых
комбинаций (2k) любого помехоустойчивого кода при заданных значениях n и dmin:
,
(4.21)
где
– число сочетаний из n элементов по i элементам.
Отсюда можно получить выражение для оценки числа проверочных символов:
.
(4.22)
Для значений (dmin / n) ≤ 0,3 разница между границей Хемминга и границей Плоткина сравнительно
невелика.
Граница Варшамова – Гильберта для больших значений n определяет нижнюю границу для числа
проверочных разрядов, необходимого для обеспечения заданного кодового расстояния:
.
(4.23)
Отметим, что для некоторых частных случаев Хемминг получил простые соотношения, позволяющие определить необходимое число проверочных символов:
r ≥ log2 (n + 1) для dmin = 3;
r ≥ log2 (2 ∙ n) для dmin = 4.
Блочные коды с dmin = 3 и 4 в литературе обычно называют кодами Хемминга.
Все приведённые выше оценки дают представление о верхней границе числа dmin при фиксированных значениях n и k или оценку снизу числа проверочных символов r при заданных k и dmin.
Существующие методы построения избыточных кодов решают, в основном, задачу нахождения такого алгоритма кодирования и декодирования, который позволял бы наиболее просто построить и реализовать
код с заданным значением dmin. Поэтому различные корректирующие коды при одинаковых dmin сравниваются
по сложности кодирующего и декодирующего устройств. Этот критерий является, в ряде случаев, определяющим при выборе того или иного кода.
Корректирующие коды Хемминга
Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока.
Поясним идею проверки на чётность на примере простейшего корректирующего кода, который так
и называется, кодом с проверкой на чётность или кодом с проверкой по паритету (равенству).
В таком коде к кодовым комбинациям безызбыточного первичного двоичного k-разрядного кода
добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или
контрольным). Если число символов «1» в исходной кодовой комбинации чётное, то в дополнительном разряде формируют контрольный символ «0», а если число символов «1» нечётное, то в дополнительном разряде формируют символ «1». В результате общее число символов «1» в любой передаваемой кодовой комбинации всегда будет чётным.
Таким
образом,
правило
формирования
проверочного
символа
cводится
к следующему:
r1 = i1
i2
...
ik,
где i – соответствующий информационный символ (0 или 1); k – общее их число, а под операцией
здесь и далее понимается сложение по модулю 2.
Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие чётности разделяет все
комбинации на разрешённые и неразрешённые. Код с проверкой на чётность позволяет обнаруживать одиночную ошибку при приёме кодовой комбинации, так как такая ошибка нарушает условие чётности, переводя разрешённую комбинацию в запрещённую.
Критерием правильности принятой комбинации является равенство нулю результата S суммирования по модулю 2 всех n символов кода, включая проверочный символ ri. При наличии одиночной ошибки S
принимает значение 1:
S = r1
i1
i2
...
ik = 0 – ошибки нет;
S = r1
i1
i2
...
ik = 1 – однократная ошибка.
Этот код является (k + 1, k)-кодом, или (n, n - 1)-кодом. Минимальное расстояние кода равно двум
(dmin = 2), и, следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на чётность может использоваться только для обнаружения (но не исправления) однократных ошибок.
Увеличивая число дополнительных проверочных разрядов и формируя по определённым правилам
проверочные символы r, равные 0 или 1, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять ошибки. На этом и основано построение кодов Хемминга.
Рассмотрим эти коды, позволяющие исправлять одиночную ошибку, с помощью непосредственного описания.
Для каждого числа проверочных символов r = 3, 4, 5... существует классический код Хемминга с маркировкой
(n, k) = (2r – 1, 2r – 1 - r),
(4.24)
т. е. – (7,4), (15,11), (31,26).
При
других
значениях
числа
информационных
символов
k
получаются
так
называемые усечённые (укороченные) коды Хемминга. Так, для международного телеграфного кода МТК-2,
имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося усечённым от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается
(укорачивается) на 6. Для примера рассмотрим классический код Хемминга (7,4), который можно сформировать и описать с помощью кодера, представленного на рис. 4.2.
Рис. 4.2
В простейшем варианте при заданных четырёх (k = 4) информационных символах (i1, i2, i3, i4) будем
полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя проверочными символами (r = 3), задавая их следующими равенствами проверки
на чётность, которые определяются соответствующими алгоритмами
r1 = i1
i2
i3;
r2 = i2
i3
i4;
r3 = i1
i2
i4,
где знак « » означает сложение по модулю 2.
На рис. 4.3 приведена схема декодера для (7,4)-кода Хемминга, на вход которого поступает кодовое
слово:
V = (i′1, i′2, i′3, i′4 , r′1, r′2, r ′3).
Апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.
Рис. 4.3
В декодере, в режиме исправления ошибок, строится последовательность:
s1 = r1’
i1’
i2’
i3’;
’
’
’
s2 = r2
i2
i3
i4’;
’
’
’
s3 = r3
i1
i2
i4’.
Трёхсимвольная последовательность (s1, s2, s3) называется синдромом. Термин «синдром» используется и в медицине, где он обозначает сочетание признаков, характерных для определённого заболевания. В
данном случае синдром S = (s1, s2, s3) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (шумовой
вектор).
Кодовые слова кода Хемминга для k = 4 и r = 3 приведены в табл. 4.1.
Число возможных синдромов определяется выражением
S = 2r.
(4.25)
При числе проверочных символов r = 3, имеется восемь возможных синдромов (2 3 = 8). Нулевой
синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определённая конфигурация ошибок, которая и исправляется. Классические
коды Хемминга (4.20) имеют число синдромов, точно равное их необходимому числу, позволяют исправить
все однократные ошибки в любом информативном и проверочном символах и включают один нулевой синдром. Такие коды называются плотноупакованными.
Таблица 4.1
k=4
i
1
i
2
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
i
3
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
4
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
r=3
r
i
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
r
2
0
0
1
1
1
1
0
0
1
1
0
0
0
0
1
1
r
3
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
Усечённые коды являются неплотноупакованными, так как число синдромов у них превышает необходимое. Так, в коде (9,5) при четырёх проверочных символах число синдромов будет равно 24 = 16, в то
время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).
Для рассматриваемого кода (7,4) в табл. 4.2 представлены ненулевые синдромы и соответствующие
конфигурации ошибок.
Таблица 4.2
Синдром
001
01
01
100
10
110
111
0
1
1
Конфигурация ошибок
Ошибка
символе
000
0001
в
00
00010
r3
00
01000
r2
0000
100
i4
10
00000
r1
001
0000
i1
010
0000
i3
i2
Таким образом, код (7,4) позволяет исправить все одиночные ошибки. Простая проверка показывает, что каждая из ошибок имеет свой единственный синдром. При этом возможно создание такого цифрового корректора ошибок (дешифратора синдрома), который по соответствующему синдрому исправляет соответствующий символ в принятой кодовой группе. После внесения исправления проверочные символы ri
можно на выход декодера не выводить. Две или более ошибки превышают возможности корректирующего
кода Хемминга, и декодер будет ошибаться. Это означает, что он будет вносить неправильные исправления и
выдавать искажённые информационные символы.
Идея построения подобного корректирующего кода, естественно, не меняется при перестановке позиций символов в кодовых словах. Все такие варианты также называются (7,4) – кодами Хемминга.
Основные выводы использования корректирующих кодов
Анализируя применение кодов, контролирующих ошибки, и корректирующих кодов в информационных системах можно сделать следующие выводы:
- можно построить такую систему связи, что вероятность ошибки при передаче данных будет достаточно малой. При этом затраты на аппаратуру будут несоизмеримо ниже, чем затраты на создание аппаратуры, повышающей соотношение сигнал – шум;
- применение кодов, контролирующих ошибки, и корректирующих кодов приводит к снижению
скорости передачи информации, и поэтому необходимо идти на определенный компромисс между скоростью
передачи информации и ее безошибочностью;
- выбор и применение типов кодов, контролирующих ошибки и корректирующих, зависит от характера возникновения ошибок, их вероятности появления и существенно влияет на ценовую и надежностную
составляющую аппаратуры кодирования-декодирования.
Учитывая изложенное, можно построить информационную систему с высокими показателями
надежности передачи информации как внутри отдельных устройств системы, так и распределенной информационной системы.
НАДЕЖНОСТЬ ПРОГРАММНЫХ КОМПЛЕКСОВ
Модели надежности программных комплексов
Для прогнозирования надёжности используемого программного комплекса могут применяться различные модели надёжности. В моделях надёжности программного комплекса используется информация о
числе ошибок, вызывающих отказы, устранённые в процессе разработки программного комплекса. На основе такой информации определяются параметры модели, которая может затем использоваться для прогнозирования ожидаемого числа ошибок (отказов программного комплекса) или некоторого другого показателя
надёжности. Показателем надёжности программного комплекса может служить вероятность отсутствия обнаружения программных ошибок в течение определённого промежутка времени при эксплуатации программы в расчётном режиме в информационной системе.
Одна из моделей основана на следующих допущениях:
- общее число команд в программе на машинном языке постоянно;
- в начале компоновочных испытаний число ошибок равно некоторой постоянной величине, и по мере исправления ошибок их становится меньше. В ходе испытаний программы новые ошибки не вносятся;
- ошибки изначально различимы, по суммарному числу исправленных ошибок можно судить об
оставшихся;
- интенсивность отказов программы пропорциональна числу остаточных ошибок.
На основе этих допущений получаем:
,
(5.1)
где t – продолжительность отладки программы, отсчитываемая от момента начала компоновки системы программного обеспечения;
– число остаточных ошибок в момент времени t, отнесённое к общему числу команд I;
– отношение числа ошибок E0, имеющихся в программе в момент t = 0, к общему числу команд на машинном языке I, т. е.
;
– суммарное число ошибок, исправленных к моменту времени t, отнесённое к общему числу команд I.
Используя последнее допущение, имеем:
,
где t – время работы системы;
(5.2)
– интенсивность отказов в течение интервалов времени t;
Ks – коэффициент пропорциональности,
Определив с помощью формулы (5.2) интенсивность отказов программы (частоту появления ошибок), найдём выражение для вероятности безошибочной работы:
.
(5.3)
Поскольку в данной модели частота появления ошибок считается независящей от времени t, она
принимается постоянной и, следовательно, среднее время безошибочной работы программы равно:
.
(5.4)
Для оценки параметров модели подставим соотношение (5.1) в формулу (5.4), получим следующие
выражение для среднего времени безошибочной работы:
.
(5.5)
Выражение (5.5) содержит два неизвестных параметра – Кs и Ео, которые можно оценить, используя
метод согласования моментов. Рассматривая два периода откладки программы t1 и t2, такие, что t1 < t2, получаем:
,
(5.6)
,
(5.7)
где t1 и t2 – продолжительность работы системы;
m1 и m2 – число ошибок в программном обеспечении, обнаруженных соответственно в периодах t1 и
t2.
Из отношений (5.6) и (5.7) следует, что
,
(5.8)
где
,
T0i – среднее время безошибочной работы, соответствующее периоду откладки программы и определяемое как T0i = ti / mi.
Заменяя отношение
на T1 в формуле (5.6), найдем Ks:
.
(5.9)
Другим методом оценивания параметров E0 и Ks является использование оценок максимального
правдоподобия.
Вторая модель, как и первая, основана на допущении об экспоненциальном распределении вероятности безошибочной работы программного комплекса.
Предполагается, что частота появления ошибок пропорциональна числу остаточных ошибок, т. е.
,
(5.10)
где
– коэффициент пропорциональности;
t – интервал времени между i-й и (i-1)-й обнаруженными ошибками.
С помощью формулы (5.10) можно найти вероятность безошибочной работы:
,
(5.11)
и среднее время безошибочной работы:
. (5.12)
Третья модель основана на допущении о том, что частота появления ошибок пропорциональна числу остаточных ошибок и времени отладки программы, т. е.
,
где t1 – промежуток времени между(i-1)-й и i-й ошибками.
Вероятность безошибочной работы равна:
(5.13)
.
(5.14)
Среднее время безошибочной работы определяется по формуле:
. (5.15)
Существуют доводы как за, так и против принятия допущения о том, что частота появления ошибок
пропорциональна времени отладки программы.
Истинную ценность той или иной модели можно измерить по её прогнозирующей способности. В
большинстве случаев, обсуждение относительной ценности моделей обычно основывается на интуиции и
проверке логической непротиворечивости. Тот факт, что число попыток экспериментально проверить эти
модели невелико, объясняется отсутствием необходимых данных об ошибках в программах или противоречивостью имеющихся данных.
Из всех рассмотренных моделей, наилучшие прогнозы остаточных ошибок для крупномасштабных
разработок программ или проектов с продолжительным периодом отладки даёт третья модель.
Следует иметь в виду, что, хотя это сравнительное исследование позволило получить некоторые полезные результаты, необходимы новые исследования такого рода.
Типы отказов и сбоев при исполнении комплекса программ
Отказы и сбои, по степени их влияния на функционирование комплекса программ и на всю систему управления в целом, делятся на несколько крупных групп:
- искажения вычислительного процесса и данных, вызывающие полное прекращение выполнения
функций системой управления на длительное или неопределённое время;
- отказ, в значительной степени обесценивающий результаты предыдущего функционирования;
искажения,
кратковременно
прерывающие
функционирование
системы
и мало искажающие накопленные данные и выдаваемые результаты;
- частичный отказ или длительный сбой, в некоторой степени, обесценивающий предыдущие результаты;
- искажения кратковременные и малоотражающиеся на вычислительном процессе и обрабатываемых данных;
- сбои, практически не обесценивающие результаты функционирования комплекса программ.
В зависимости от глубины контроля и длительности запаздывания в обнаружении отказа, а также в
зависимости от качества средств, осуществляющих восстановление, одни и те же ситуации искажений могут
быть отнесены к разным типам отказов или сбоев. Наиболее типичными полными отказами при функционировании сложных комплексов программ являются:
- зацикливание, т. е. последовательное, повторяющееся исполнение группы команд, которое не прекращается без внешнего вмешательства, блокируя функционирование всех остальных программ данного
комплекса;
- остановка ЭВМ и полное прекращение решения функциональных задач, при этом может сохраниться возможность приёма и выдачи информации и выполнения некоторых функций, стимулируемых прерываниями;
- значительное искажение или полная потеря накопленных данных о состоянии внешних абонентов
и процессе их функционирования;
- прекращение или недопустимое снижение темпа решения некоторых задач, пропуск или потеря
необработанных групп сообщений вследствие перезагрузки ЭВМ.
Эти отказы существенно влияют на выполнение основных функций комплексом программ. В несколько меньшей степени, на вычислительный процесс и обрабатываемые данные влияют искажения, приводящие к следующим типам частичных отказов или длительных сбоев:
- искажения заданной последовательности вызова подпрограмм, приводящие к пропуску исполнения отдельных подпрограмм или их частей, что приводит, в свою очередь, к неправильному или неполному
решению некоторых задач и к искажению выходных данных;
- использование и обработка искажённых исходных данных, отражающиеся на логике решения задач и приводящие к искажению отдельных накопленных и выдаваемых данных.
Эти типы искажений заключаются в кратковременном нарушении нормального вычислительного
процесса, либо в искажении исходных, промежуточных или результирующих данных. В зависимости от повторяемости и глубины распространения, искажения квалифицируются как частичные отказы, либо как отказы с длительными последствиями.
В наименьшей степени на надёжность функционирования информационных систем влияют сбои,
которые незначительно искажают общие результаты. Не нарушая практически логики функционирования
комплекса программ, такие сбои искажают преимущественно отдельные обрабатываемые и результирующие данные. При поступлении аналогичных данных, в последующие моменты времени можно ликвидировать последствия сбоев, не проводя специальных восстановительных работ.
Основные факторы, влияющие на надежность функционирования комплекса программ
Одни и те же типы сбоев и отказов при исполнении комплексов программ могут быть вызваны различными факторами, которые можно разделить на три группы. В первую группу входят факторы, непосредственно вызывающие сбой или отказ при исполнении программы, причинами которых могут быть:
искажение
исходной
информации,
поступающей
от
внешних
абонентов,
в том числе, и ошибочные действия операторов;
- самоустраняющиеся отказы или сбои в вычислительной системе;
- невыявленные ошибки в комплексе программ.
Ко
второй
группе
факторов
относятся
архитектура
комплекса
программ
и структурное построение его компонент. Структура программ определяет возможность расширения последствий искажений информации или вычислительного процесса, влияет на вероятность превращения искажения в отказ и на время восстановления после отказа.
Третья группа факторов влияет на длительность восстановления и глубину последствий от возникающих отказов. В эту группу входят факторы, определяющие качество контроля вычислительного процесса и обрабатываемых данных, запаздывание в обнаружении искажений, качество классификации искажений
и длительность проявлений их последствий. Они определяют длительность восстановления, время наработки на отказ и способствуют быстрой локализации искажений.
Искажения исходной информации, в большинстве случаев, не влияют на надежность выполнения
программ. Причинами искажений данных, поступающих от внешних абонентов, могут быть:
- искажение данных на первичных носителях информации;
- сбои и частичные отказы в аппаратуре ввода данных с первичных носителей информации;
- шумы и сбои в каналах связи при передаче или приёме телекодовой информации;
- потери или искажения сообщений в ограниченных буферных накопителях вычислительной системы;
ошибки
в
документах,
используемых
для
подготовки
данных,
вводимых
в вычислительную систему.
Самоустраняющиеся отказы и сбои в аппаратуре вычислительных систем являются фактором, существенно влияющим на надёжность функционирования комплексов программ. Значительно чаще происходят сбои или трудно обнаруживаемые кратковременные отказы. Большинство из них выявляется и устраняется средствами аппаратурного контроля и не влияет на исполнение программ. Однако, некоторая часть аппаратурных сбоев может приводить к искажениям переменных. Причинами таких сбоев и отказов являются
преимущественно внешние воздействия на аппаратуру, влияющие на нарушение контактов и пропадание
сигналов, или индустриальные электрические помехи. Чаще происходят сбои, которые не удаётся обнаружить и зафиксировать при функционировании комплекса программ в процессе нормальной обработки информации и управления. Такие сбои проявляются в случайные промежутки времени, и практически невозможно
добиться их повторяемости.
Невыявленные ошибки являются основной причиной ненадёжности функционирования. В процессе
отладки основная часть ошибок в программах обнаруживается и устраняется, но есть риск пропуска нескольких ошибок. Любая отладка «может показать наличие ошибок, но не может показать их отсутствие». В
процессе тестирования и отладки программ практически невозможно выполнение абсолютно полных проверок. В результате в программах всегда существует некоторое количество невыявленных ошибок.
Обеспечение надежности и повышение качества программ
Моделирование является лишь одним аспектом обеспечения надёжности программных комплексов
и имеет цель – прогнозирование числа ошибок, остающихся в системе, на основе использования статической информации о процессе обнаружения и устранения ошибок. Не менее важное значение имеют две другие области обеспечения надёжности программных средств, безошибочное проектирование и испытания,
ориентированные на обеспечение надёжности.
Вероятно, самым лучшим способом получить надёжное программное обеспечение является сведение
к
минимуму
числа
ошибок
и
их
последствий
в ходе разработки комплекса программ. Однако не существует какого-либо проверенного способа создания
надёжного программного обеспечения. Отсутствует пока и какая-либо теоретическая основа методики разработки безошибочных программ. Тем не менее, по общему мнению, существует целый ряд методов разработки программ и управления этим процессом, которые позволяют создавать надёжные программы. К этим
методам, обычно, относится структурное программирование и некоторые, связанные с ним приёмы.
Идея структурного (модульного) программирования базируется на стремлении упорядочить сложные комплексы программ и их проектирование. Строгое определение термина «структурное программирование» не существует. Имеется несколько определений структурного (модульного) программирования. Чаще всего оно определяется как программирование без использования операторов GO TO, с применением
нисходящего метода разработки программ и с использованием принципа модульного конструирования программ. Указанные три приёма повышают надёжность, удобочитаемость и удобство обслуживания программного обеспечения.
Программирование без использования операторов GO TO. Сам по себе оператор безусловного перехода не приводит к ошибкам. Однако передача управления с помощью этого оператора может вызвать
усложнение логической схемы программы и сделать её трудночитаемой. Наоборот, исключение операторов
GO TO позволяет получить более понятную и удобочитаемую программу. Кроме того, программу, не содержащую операторов безусловного перехода, легче проверить.
Нисходящее программирование. По существу, имеется два способа составления программ: снизу
вверх и сверху вниз. Классическим способом составления большинства программ является движение снизу
вверх. При таком подходе руководитель группы программистов рассматривает проект в целом, формулирует цели системы, а затем определяет элементы, необходимые для системы программного обеспечения. Задаются средства сопряжения, и отдельные части программы распределяются между программистами. Каждый программист отвечает за проверку своей подсистемы или модуля до момента объединения последних в
единую систему. Интеграция модулей в систему выполняется последовательно по уровням и поручается
самому квалифицированному из авторов стыкуемых программ. Такой подход к составлению программ аналогичен способу разработки аппаратного оборудования.
Более надёжные программные комплексы позволяет получить «нисходящее» программирование. В
этом случае руководитель группы программистов не только осуществляет контроль над работой, но и участвует в составлении программ.
Модульное конструирование программ. Обычно при составлении сложной программы её разбивают на отдельные модули так, что каждый из них может использоваться во многих других. Но при этом уве-
личивается вероятность возникновения всякого рода недоразумений и ошибок. Этот источник ошибок можно свести к минимуму, если вход в каждый модуль будет осуществляться только в его начало (сверху), а
выход только в его конец (снизу).
Структурирование данных. Неотъемлемой компонентой комплексов программ являются данные,
которые поступают на обработку, преобразуются, хранятся и выдаются внешним абонентам. Структурирование данных способствует уменьшению сложности комплекса программ и снижает вероятность появления
ошибок из-за неправильного использования. В ряде систем сложность массивов данных превышает логическую сложность программ и обуславливает основную массу ошибок, выявляемых в процессе отладки. Поэтому большое значение при проектировании программ имеет строгое описание переменных и простота
структурного построения массивов.
Всю совокупность данных можно разделить на два иерархических уровня: простые переменные и
массивы. Простые переменные представляют собой минимальную компоненту данных, имеющую имя и
описание. Массивы образуются из нескольких простых переменных по некоторым правилам объединения и
упорядочивания и имеют собственное описание, структуру и имя. Основными символами для описания данных являются буквы, цифры и ограничители. Наиболее часто используются следующие типы переменных:
- вещественные, принимающие действительные положительные и отрицательные значения в заданных пределах;
- целые, в заданных интервалах принимающие только целые положительные и отрицательные численные значения;
- булевы, принимающие только два значения: да или нет (истина или ложь);
- двоичные, представляющие собой последовательность бит;
- символьные, образующиеся из последовательности байтовых кодов, каждый из которых соответствует некоторому символу языка программирования или описания данных.
Из простых переменных по заданным правилам упорядочения образуются массивы, размеры которых задаются списками граничных пар. Структура массивов и правила упорядочения переменных различны
и определяются следующими факторами:
- типами и структурой простых переменных, а также областью значений, которые могут принимать
переменные;
- мощностью массива – наибольшим числом значений, которые могут принимать переменные, а
также объемом памяти, необходимым для хранения массива в любой момент времени;
- способом заполнения и уплотнения переменных в памяти, используемой для хранения массива;
- методом и частотой заполнения и выборочного обновления компонентов массива и затратами производительности ЭВМ, необходимыми для обращения к массиву;
- типом реальной памяти, используемой для хранения массива.
Для повышения надёжности комплексов программ целесообразно использовать простейшие структуры массивов. При работе с массивами наибольшие затраты производительности ЭВМ связаны с поиском
простых переменных или частных массивов, признаки которых удовлетворяют некоторому условию.
Тестирование и испытание программ
Вполне вероятно, что даже при использовании самых лучших способов программирования, программные комплексы всё же будут содержать те или иные ошибки. Целью испытаний программы является
подтверждение того, что она соответствует проектным замыслам. Любая корректировка программы может
быть сведена к трём типовым операциям:
- исключение части или всей подпрограммы;
- вставка компонент или новой целой подпрограммы на имеющееся свободное место;
- замена части или всей подпрограммы в пределах освобождающегося свободного места или с расширением программы и использованием дополнительной памяти.
Необходимые исправления вводятся в текст программы, программа перетранслируется и повторно
тестируется данными. После подтверждения правильности выполненной корректировки продолжается отладка по новым тестам, либо программа передаётся на эксплуатацию. В больших комплексах программ внесение изменений усложняется и требует проведения дополнительных работ. Роль дополнительных работ
возрастает, когда комплекс программ отлажен и проводятся завершающие стадии проверок. Экспериментальный анализ выполненных при этом корректировок показывает, что около 30% внесённых изменений
являются неправильными и не устраняют ошибку, либо вносят новую ошибку в программу. Эти новые
ошибки трудно обнаружить, так как их последствия не проявляются на тестах повторяющихся проверок и
связаны
с функционированием комплекса программ в иных режимах. Поэтому при корректировке программ необходимы дополнительные работы по анализу возможных последствий внесённых изменений.
Средства проверки состоят из двух основных модулей: инструментального модуля и анализатора.
Исходная программа испытуемого модуля вначале поступает в инструментальный модуль, который снабжает проверяемый модуль дополнительными операторами. Эти операторы называются датчиками и счётчиками, а сам процесс введения указанных операторов носит название инструментального оснащения. В процес-
се инструментального оснащения исходной программы её функции должны оставаться неизменными, т. е.
оператор-датчик и оператор-счётчик не должны менять функционального назначения программы. Снабжёнными дополнительными операторами блок программы транслируется обычным способом, а полученная выходная программа прогоняется с использованием её тестовых данных. При этом на выходе программы, помимо обычных результатов, получают также инструментальный файл данных. Затем этот инструментальный файл данных и файл данных исходной программы, снабжённый дополнительными операторами, вводятся в модуль анализатора, который выдаёт на выходе сведения о поведении испытуемого модуля в процессе его выполнения. В каждом таком отсчёте содержится информация о числе случаев появления каждого
оператора, числе случаев выбора конкретного маршрута в каждой точке ветвления и о времени, необходимом для выполнения каждого оператора. Подобная информация используется при проверке структуры программы; она даёт уверенность в правильности логики и кода программы, гарантирует, что каждый оператор
и каждое ответвление программы выполняется хотя бы один раз. Можно также обеспечить вызов хотя бы
один раз каждой подпрограммы. Длительность испытаний зависит от конфигурации системы
и состава испытаний, но типичным можно считать период, включая испытания в условиях пользователя от 1
до 6 месяцев, иногда и более.
Критерии надежности программных комплексов
При разработке технических требований на надёжность программных комплексов следует принимать во внимание следующие критерии:
- корректность программного обеспечения – число серьёзных ошибок в индивидуальном программном
пакете и время, необходимое для их исправления;
- обслуживаемость системы – влияние ошибок программного комплекса на обслуживаемость системы;
- безотказность системы – частота системных (или подсистемных) отказов, вызываемых ошибками
программного обеспечения.
С учётом сложившейся реальности при выборе критериев оценки надёжности необходимо принимать во внимание следующие.
Новое программное обеспечение может требовать в первое время менее жёстких критериев и большего времени для его совершенствования.
На короткое время, после выпуска новой версии программного обеспечения, также могут потребоваться менее строгие критерии его качества.
Разбросы, вызываемые различием в условиях применения и использования.
Эффективность работ по исправлению ошибок программного обеспечения, проводимых пользователем, зависит от воспроизводимости ошибок, что, в свою очередь, зависит от информации, поступающей от
пользователя.
Возможны и другие требования, которые следует принять во внимание, например, связанные с
быстродействием и производительностью. Может случиться, что подобные критерии достигаются только за
счёт большого числа остающихся некорректностей или низкой безотказности и обслуживаемости системы.
КОНТРОЛЬ И ДИАГНОСТИКА ИНФОРМАЦИОННЫХ СИСТЕМ
Содержание технической диагностики
Объектом технического диагностирования называется изделие, его составные части, техническое
состояние которых подлежит определению. Техническое диагностирование представляет собой процесс
определения технического состояния объекта диагностирования. Завершением процесса диагностирования
является установление вида технического состояния. Различают следующие виды технического состояния: работоспособное и неработоспособное, исправное и неисправное, правильное функционирование и неправильное
функционирование.
Объект должен удовлетворять требованиям, установленным технической документацией. Возникающие в объекте дефекты нарушают это соответствие. Задача диагностирования состоит в том, чтобы своевременно обнаружить дефекты, найти места и причины их возникновения, восстановить нарушенное дефектами соответствие объекта техническим требованиям.
Чтобы убедиться, что объект исправен, то есть, в нем нет ни одной неисправности, проводят проверки исправности. Исправленный объект всегда работоспособен и функционирует правильно.
Техническое диагностирование с целью определения мест, причин и вида дефектов объекта называется поиском дефектов.
Техническое диагностирование осуществляется с помощью технических средств.
Различают системы тестового диагностирования, когда на объект подают специально организованные тестовые воздействия от средств диагностирования и функционального диагностирования, когда на
объект поступают только рабочие воздействия.
Обобщенная схема функционального диагностирования (рис. 6.1).
Внешнее воздействие
Рис. 6.1
Реакция
Обобщенная схема тестового диагностирования (рис. 6.2).
Тест
Реакция
Рис. 6.2
Функциональная диагностическая модель
При поиске неисправности аппаратуру представляют в виде функциональной модели. Строят несколько функциональных моделей: для устройства в целом с глубиной поиска неисправности до блока или
модуля, для каждого блока или модуля, с глубиной поиска до каскада или отдельного компонента.
Исходными данными для построения функциональной диагностической модели являются:
1) функциональная схема объекта контроля и диагностики;
2) принципиальная схема объекта контроля и диагностики;
3) описание процессов, протекающих в объекте диагностирования;
4) заданная глубина поиска неисправностей.
При построении функциональной модели пользуются следующими правилами:
1) в каждом функциональном элементе должны быть известны значения (номинальные допуски)
входных и выходных параметров, их функциональная зависимость и способ контроля;
2) функциональный элемент модели объекта диагностирования считается неисправным, если при
всех входных сигналах, лежащих в допустимых пределах, на его выходе появляется сигнал, значение которого выходит из допустимых пределов;
3) значения внешних входных сигналов всегда находятся в пределах допусков;
4) линии связи между функциональными элементами считаются абсолютно надежными;
5) любой функциональный элемент модели может иметь только один выходной сигнал при произвольном конечном числе входных сигналов. Если у блока несколько выходов, то такой блок разбивается на
несколько блоков по числу контролируемых выходов. У каждого блока оставлены только те входы, которые
формируют данный выход. Функциональная модель выполняется в виде графической схемы, на которой
каждый функциональный элемент обозначается в виде прямоугольника с некоторым количеством входных
сигналов (входных стрелок) и одним выходным сигналом (выходной стрелкой);
6) при выходе из допустимых пределов хотя бы одного из входных сигналов появляется выходной
сигнал, который также выходит из допустимых пределов.
Выход любого функционального элемента можно соединять с любым числом входов, а вход любого
элемента соединяют только с одним выходом.
Входы, не соединенные ни с одним выходом, называются внешними. Они передают внешнее воздействие на диагностируемый объект. Внешнее воздействие обозначается через xij, где i – номер функционального элемента, j – номер входа этого элемента. Вход функционального элемента обозначается zi, где i –
номер функционального элемента.
Построение таблицы неисправностей или матрицы состояний
В системе маловероятно одновременное появление двух отказов. Для каждого элемента возможны
два альтернативных исхода (исправен – неисправен).
Число различных состояний диагностируемой системы с учетом отказов одновременно одного
функционального элемента сводится в таблицу состояний или матрицу неисправностей. Число строк матрицы равно числу функциональных элементов системы. Число столбцов равно числу выходных сигналов системы.
Пусть неисправен i-й функциональный элемент. Этому состоянию соответствует недопустимое значение выходного сигнала zi и на пересечении si строки и zi столбца записывается 0. Если при этом любой j-й
функциональный элемент имеет так же недопустимое значение zj, то на пересечении si строки и zj столбца
так же записывают 0. Если значение выходного сигнала в допуске, на пересечении записывают 1.
Полученная матрица неисправностей используется при разработке программ поиска неисправностей.
Основные способы построения алгоритмов поиска неисправностей
При построении алгоритма способом последовательного функционального анализа предварительно
определяются, исходя из назначения информационной системы, основные параметры, характеризующие
исправность системы. Последовательно контролируя сигналы на выходе каждого элемента системы, можно
определить неисправный элемент.
Способ последовательного функционального анализа прост, нагляден. Полученный с использованием этого способа алгоритм поиска неисправностей не оптимален ни во времени, ни по средним затратам.
Способ половинного разбиения используется при разработке алгоритмов поиска неисправностей в
информационных системах с последовательно соединенными элементами.
Диагностируемая информационная система, состоящая из N последовательно включенных элементов, неработоспособна из-за отказа i-го элемента (i = 1, 2, … , N). Целесообразно контролировать такой выходной сигнал, который разбивает объект диагностики пополам. Каждый последующий параметр для
контроля выбирается аналогично, т. е. делят пополам образующуюся систему после выполнения предыдущей проверки, в зависимости от результатов её исхода.
Способ построения алгоритма поиска неисправностей на основе информационного критерия позволяет выбрать минимальное количество контролируемых параметров и определить последовательность их
контроля.
Исходные данные для этого способа задаются в виде функциональной модели диагностируемой системы и таблицы неисправностей. Таблицы составляются в виде транспонированной матрицы состояний,
где столбцы соответствуют всем возможным состояниям диагностируемого объекта, а строки – выходным
сигналам функциональных элементов. Контроль может иметь два исхода: параметр в допуске – 1, или параметр не в допуске – 0.
Диагностируемый объект разделяется на N элементов, вероятности состояний которых одинаковы.
P(S1) = P(S2) = … = P(SN) = 1/N.
Энтропия системы с равновозможными состояниями:
Результат контроля k-го параметра диагностируемого объекта даёт некоторое количество информации о нем.
Количество информации измеряют уменьшением энтропии исследуемой системы,
I k = H 0 – H k,
где Hk – средняя условная энтропия диагностируемого объекта при условии контроля k-го выходного сигнала; Ik – количество информации.
Поскольку, в результате контроля принимаются лишь два решения, то средняя энтропия:
где
и
– вероятности положительного и отрицательного решений;
и
– энтропии, соответствующие диагностируемому объекту после выполнения контроля выходного
сигнала Zk.
Вероятности
и
находятся по матрице состояний, как отношение числа единиц M и нулей N – M к общему числу состояний N в k-й строке.
;
.
Тогда
Контроль k-го выходного сигнала дает следующее количество информации:
Последовательно вычисляем значения Ik (где k = 1, 2, …, N) и по убывающей определяем значимость выходного сигнала Zk.
Первым контролируется сигнал Zk, дающий наибольшее количество информации.
После контроля 1-го параметра определяем количество информации, получаемое при контроле каждого оставшегося параметра относительно состояния, характеризующегося энтропией
тропия
Условная эн-
где
– вероятность положительного решения при контроле параметра Zn; m1 – количество единиц в n-й строке таблицы состояний относительно m единиц в k-й строке, m2 – количество единиц в n-й строке относительно N – m нулей k-й строки.
;
Выражение для вычисления количества условной информации имеет вид:
По максимуму условной информации выбирается второй контролируемый параметр. По такой же
схеме выбираются остальные параметры.