Ващенко Г.В., Добронец Б.С. Надежность информационных систем. Лабораторный практикум

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

u(0, t) = u

(t), t ∈ [0, T ],

u(1, t) = u

(t), t ∈ [0, T ],

Предположим, что коэффициенты уравнения и граничные функции удовле-

творяют условиям

q, f ∈ C(Q), u

, u

∈ C

([0, T ]).

Пусть коэффициент p(x, t) имеет разрыв первого рода на прямой x = ξ,

поэтому на линии разрыва вместо уравнения (70) выполняются условия

[u]

= 0, [p∂

= 0, ∀t ∈ [0, T ], (72)

где [f]

= lim

x→ξ−0

f(x)−lim

x→ξ+0

f(x). Линия x = ξ делит Q на две подобла-

сти Q

, Q

, и для коэффициента p предполагаются выполненными следующие

условия: p, ∂

p ∈ C

), i = 1, 2, причем для каждой из подобластей Q

на

линии x = ξ значение функции берется равным пределу по соответствующей

подобласти. В этом смысле понимается условие

∂

u, ∂

u ∈ Q

, i = 1, 2,

которое считается выполненным при дальнейшем изложении.

Введем равномерную сетку ω

на отрезке [0, 1] с шагом h = 1/n, целым

n ≥ 2 и предположим, что ξ ∈ ω

. Это предположение не ограничивает общ-

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

в каждой зоне гладкости и переводящее ξ в любую заданную точку. Кро-

ме того, введем равномерные сетки по времени ω

, ω

и на прямоугольнике

Q : ω

hτ

= ω

× ω

Приближенное решение будем искать в соответствии с явной схемой

= Lu

+ f на ω

hτ

, (73)

где разностные операторы вводятся по формулам

= (pu

)

− qu

u(x + h/2) − u(x − h/2)

u(t) − u(t − τ)

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

(x, 0) = 0, x ∈ ω

(0, t) = u

(t), u

(1, t) = u

(t), t ∈ ω

Известна следующая оценка погрешности:

||u − u

∞,ω

hτ

≤ c(h

+ τ), (74)

где c не зависит от h, τ .

Задания

Использование правила Рунге для определения точности вычислений.

1. Численное решение задачи Коши для системы ОДУ.

2. Численное интегрирование функций.

3. Численное интерполирование функций.

4. Численное решение одномерного уравнения теплопроводности.

5. Представить множество решений системы линейных алгебраических

уравнений в графическом виде

Ax = b

с матрицей A и правой частью b.

Решить систему линейных алгебраических уравнений методом Гаусса.

Найти LU разложение системы линейных алгебраических уравнений.

A =







[2, 3] [−1, 1]

[−1, 1] [2, 3]







, b =







[0, 1]







A =







[2, 3] [0, 1]

[−1, 1] [2, 3]







, b =







[0, 1]







A =







[2, 3] [−1, 1]

[−1, 0] [2, 3]







, b =







[−1, 1]







A =







[2, 3] [−1, 0]

[0, 1] [2, 3]







, b =







[−1, 1]







A =







[3, 4] [−2, 1]

[−1, 1] [2, 3]







, b =







[−1, 1]







A =







[2, 3] [−1, 1]

[−1, 1] [3, 4]







, b =







[−1, 1]







Лабораторная работа № 9.

Надежность при передаче данных, резервирование.

Цель работы: Закрепление знаний по теме “Контроль и диагностика ИС”.

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

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

стирования программ с однократными ошибками.

Самостоятельная работа студента под контролем преподавателя. Со-

стоит в применении ПО для резервирования и сжатия информации различ-

ных форматов. Применении методов обнаружения и исправления однократ-

ных ошибок

Форма отчетности: Резервные копии программ. Отчет об обнаружении

ошибок.

Элементы теории кодирования

В теории передачи информации чрезвычайно важным является решение

проблемы кодирования и декодирования, обеспечивающее надежную переда-

чу по каналам связи с “шумом”.

Передача информации сводится к передаче по некоторому каналу свя-

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

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

будет восприниматься неправильно. Например, в системе ЭВМ — ЭВМ од-

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

Канал связи в этом случае физически реализуется электромагнитным по-

лем между поверхностью Земли и спутником. Электромагннтные сигналы,

накладываясь на внешнее поле, могут исказиться и ослабиться. Для обес-

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

эффективные методы, использующие коды различных типов.

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

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

двух символов {0, 1}. Он называется двоичным алфавитом. Тогда сообще-

ние есть конечная последовательность символов этого алфавита. Сообще-

ние, подлежащее передаче, кодируется по определенной схеме более длинной

последовательностью символов в алфавите {0, 1}. Эта последовательность

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

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

информацию, содержащуюся в дополнительных: символах. Принятая после-

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

большой вероятностью совпадающее с переданным.

Блочный двоичный (m, n)-код определяется двумя функциями: E, F.

Функция Е определяет схему кодирования, а функция D — схему декоди-

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

схемы

Сообщение →

Кодированное сообщение →

Канал связи →

T →

Принятое сообщение →

Декодированное сообщение

Здесь Т — “функция ошибок”: Е и D выбираются таким образом, чтобы

композиция D · T · E была функцией, с большой вероятностью близкой к

тождественной. Двоичный (m, n)-код содержит 2

кодовых слов.

Коды делятся на два больших класса: коды с обнаружением ошибок,

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

сообщении, и коды с исправлением ошибок. которые с большой вероятностью

могут восстановить посланное сообщение.

Пример 1.

1. Код с проверкой четности. Это пример простого кода, с “большой

вероятностью указывающего на наличие ошибки.

Пусть a = a

...a

— сообщение длины m.

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

E(a) = b = b

...b

m+1

где a

= b

, i = 1...m .

m+1

= 0, если сумма b

— четное число,

m+1

= 1, если сумма b

— нечетное число.

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

D(b) = c = c

...c

где c

= b

при i = l, ..., m.

Например, при m =2 E(00) = 000, E(01) =011. E(10) = 101, E(11) =

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

должна быть четной. Если сумма нечетная, то это означает, что при передаче

сообщения произошла ошибка. Однако, если сумма четная, то это еще не

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

ошибках и вообще любом четном их числе.

2. Код с тройным повторением. Это пример весьма неэкономного

кода с исправлением ошибок.

Схема кодирования, т. е. функция E, определяется таким образом: каж-

дое сообщение разбивается на блоки длины m и каждый блок передается

трижды. Схема декодирования, т. е. функция D, определяется следующим

образом: принятое сообщение разбивается на блоки длины 3m и в каждом

блоке из трех символов b

, b

i+m

, b

i+2m

, принимающих значение 0 или 1, выби-

рается тот, который встретился большее число раз (два или три раза). Этот

символ считается i-м символом в декодированном сообщении.

Можно определить также (1, r)-код с r-кратным повторением, в котором

каждый символ 0 или 1 кодируется последовательностью из r таких символов.

При декодировании решение принимается “большинством голосов”, т. е. пере-

данным считается символ, встречающийся большее число раз. При больших

r мы практически обезопасим себя от ошибок, однако передача сообщений

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

Расстояние Хемминга

На множестве двоичных слов длины m расстоянием d(a, b) между сло-

вами a и b называют число несовпадающих позиций этих слов, например:

расстояние между словами a=01101 и b=00111 равно 2.

Определенное таким образом понятие называется расстоянием Хеммин-

га. Оно удовлетворяет следующим аксиомам расстояний:

1) d(a, b) ≥ 0 и d (a, b) = 0 тогда и только тогда, когда a = b;

2) d(a, b) = d(b, a);

3) d(a, b) + d(b, c) ≥ d(a, c) (неравенство треугольника).

Весом w(a) слова называют число единиц среди его координат. Тогда

расстояние между словами и b есть вес их суммы w(a ⊕b): d(a, b ) = w(a ⊕b),

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

лю 2.

Интуитивно понятно, что код тем лучше приспособлен к обнаружению

и исправлению ошибок, чем больше различаются кодовые слова. Понятие

расстояния Хемминга позволяет это уточнить.

Теорема 1. Для того чтобы код позволял обнаруживать ошибки в k

(или менее) позициях, необходимо и достаточно, чтобы наименьшее рас-

стояние между кодовыми словами бы ≥ k + 1.

Доказательство этой теоремы аналогично доказательству следующего

утверждения.

Теорема 2.Для того чтобы код позволял исправлять все ошибки в k

(или менее) позициях, необходимо и достаточно, чтобы наименьшее рас-

стояние между кодовыми словами было ≥ 2k + 1.

Действительно, если наименьшее расстояние между кодовыми словами

≥ 2k + 1, то для любых кодовых слов и b имеем d(a, b) ≥ 2k + 1. Пусть

при передаче некоторого слова произошло r ≤ k ошибок, в результате чего

было принято слово . Тогда d(a, c) = r ≤ k. Из неравенства треугольника

(аксиомы 3) следует, что d(a, c)+d(c, b) ≥ d(a, b ) ≥ 2k+1. Отсюда расстояние

d(c, b) от слова до любого другого кодового слова b больше k. Значит, для

декодирования посланного слова надо найти кодовое слово a, ближайшее к

принятому слову c в смысле расстояния Хемминга.

Если наименьшее расстояние между кодовыми словами меньше, чем 2k+

1, то найдутся такие два кодовых слова a и b, расстояние между которыми

будет ≤ 2k. Тогда, если в кодовом слове будет k ошибок, принятое слово c

находится от другого кодового слова b на расстоянии, не большем, чем от a.

Поэтому нельзя определить, какое из слов (a или b) было передано.

В математической модели кодирования и декодирования удобно рассмат-

ривать строки ошибок. Данное сообщение a = a

...a

кодируется кодовым

словом b = b

...b

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

ошибок e = e

...e

так что приемник принимает сигнал c = c

...c

, где

= b

+ e

. Система, исправляющая ошибки, переводит слово c = c

...c

ближайшее кодовое слово b = b

...b

. Система, обнаруживающая ошибки,

только устанавливает, является ли принятое слово кодовым или нет. Послед-

нее означает, что при передаче произошла ошибка.

Пример 2.

1. Рассмотрим (2, 3)-код с проверкой четности. Тогда (см. пример 2.)

множество кодовых слов есть 000, 101, 011, 110. Минимальное расстояние

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

нократную ошибку.

2 Рассмотрим (2, 5)-код со схемой кодирования E(00) = 00000 = b

;

E(01) = 01011 = b

; E(10) = 10101 = b

; E(11) = 11110 = b

. Минимальное

расстояние между кодовыми словами равно трем. Этот код способен исправ-

лять однократную ошибку. Однократная ошибка приводит к приему слова,

находящегося на расстоянии 1 от единственного кодового слова, которое и

было передано.

Матричное кодирование

При явном задании схемы кодирования в (m, n )-коде следует указать 2

кодовых слов, что весьма неэффективно.

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

методика матричного кодирования.

Пусть G = (gij) — матрица порядка mn с элементами g

, равными 0

или 1. Символ ⊕ обозначает сложение по модулю 2. Тогда схема кодирования

задается системой уравнений в матричной форме

b = aG,

где a — вектор, соответствующий передаваемому сообщению; b — вектор,

соответствующий кодированному сообщению; G — порождающая матрица

кода.

Порождающая матрица кода определена неоднозначно. Код не должен

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

Можно доказать, что этого не произойдет, если первые m столбцов матрицы

G образуют единичную матрицу.

Заметим, что вместо 2

кодовых слов достаточно знать m слов, являю-

щихся строками матрицы G.

Пример 3.

1. Порождающей матрицей (1,r)-кода с повторением является матрица

G = (1...1),

так как 1...1 = 1G, 0...0=0G.

2. Порождающей матрицей (2, 3)-кода с проверкой четности является

матрица

G =





1 0 1

0 1 1





3. Рассмотрим матрицу G порядка 3 × 6:

G =







1 0 0 1 1 0

0 1 0 0 1 1

0 0 1 1 1 1







Сообщения a

= 100, a

= 010, a

=001 кодируются соответственно пер-

вой, второй и третьей строками матрицы G. Полны;; список кодирования

= 000 → 000000;

= 100 → 100110;

= 010 → 010011;

= 110 → 110101;

= 001 → 001111;

= 101 → 101001;

= 011 → 011100.

= 111 → 111010;

Групповые коды

Двоичный (m, n)-код называется групповым, если его кодовые слова об-

разуют группу.

Заметим, что множество всех двоичных слов длины m образует ком-

мутативную группу с операцией покоординатного сложения по модулю 2, в

которой выполняется соотношение a⊕a = 0. Следовательно, множество слов-

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

Пусть G — порождающая матрица кода порядка m×n. Тогда множество

кодовых слов b = aG есть группа.

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

но наименьшему весу ненулевого кодового слова. Следовательно, код, рас-

смотренный в примере 2. способен исправлять однократную ошибку и обна-

руживать двойную, так как наименьший вес кодового слова равен 3.

Пусть задан групповой код с порождающей матрицей G и кодирование

происходит по схеме b = aG.

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

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

Это есть множество всех двоичных слов длины n. Оно образует коммута-

тивную группу. Множество всех кодовых слов есть подгруппа . Рассмотрим

множество смежных классов по , т. е. фактор-группу С/В. Лидером смеж-

ного класса назовем слово, имеющее наименьший вес. Поскольку смежные

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

представляется в виде суммы c = e + b. Декодирование слова состоит в вы-

боре кодового слова b в качестве переданного и в последующем переходе к

слову a, где b = E(a).

Данный метод кодирования удобно реализовать с помощью таблицы:

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

смежный класс 0+B, а остальные строки соответствуют остальным смежным

классам по B, причем первый столбец этой таблицы есть столбец лидеров.

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

выбрать в качестве переданного кодовое слово b находящееся в первой строке

того же столбца, что и . Например, если принято слово 110011, то считается,

что передано слово 010011; если принято слово 100101, то передано слово

110101, а если принято слово 110101, то считается, что оно и было передано.

1 Покажем, что при таком способе декодирования:

исправляются все строки ошибок, являющиеся лидерами;

кодовое слово, стоящее в данном столбце, является ближайшим кодовым сло-

вом ко всем словам этого столбца.

Коды Хемминга

Опишем один из классов групповых кодов — коды Хемминга которые ис-

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

равен 3. Это (m, n)-коды, где m = 2

− r − 1, n = 2

− 1 для любогоr ≥ 2.

Схема кодирования:

1. Сообщения — слова длины m = 2

−r −1, кодовые слова имеют длину

n = 2

− 1.

2. В каждом кодовом слове символы, индекс, которых являются степенью

двойки, т. е. b

, b

, ... — контрольные, а остальные — символы сообще-

ния, расположенные в том же порядке. Например, при r=4 b

, b

—

контрольные символы, b

, b

, ... — символы сообщения.

3. Рассмотрим матрицу порядка гХ (2—1) такую, что ь г’-м столбце этой

матрицы стоят символы двоичного разложения числа i. Тогда матрицы M

при r = 2, 3, 4 имеют соответственно вид





0 1 1

1 0 1





;







0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1







4. Запишем систему уравнений

Mb = 0.

Например, при r = 3, эта система имеет вид

+ b

= 0,

+ b

= 0,

+ b

= 0.

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

входит один и только один символ b

индекс которого есть степень двойки.

5. При кодировании сообщения значения контрольных символов получим

из системы Mb = 0..

Схема декодирования

Пусть принято слово c = b + e, где b— кодовое слово, c — ошибка. Тогда

Mb = 0, и, следовательно, Mc = Me

Если Me = 0, то считается, что ошибки не было. Это дейвительно так

при е = 0.

Если произошла ошибка ровно в одной позиции, т. е. вектор ошибок e

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

столбцом матрицы M. В этом случае в переданном слове c надо изменить

символ в i-й позиции и вычеркнуть контрольные символы. Тогда полученное

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

Если ошибка допущена более чем в одной позиции, декодирование дает

неверный результат.

Задания

1. Напишите программу для обнаружения однократной ошибки на ос-

нове контроля четности.

2. Напишите программу для обнаружения однократной ошибки на ос-

нове группового кодирования.

3. Напишите программу для обнаружения однократной ошибки на ос-

нове кодов Хеминга.

4. Напишите программу для исправления однократной ошибки на основе

кодов Хеминга.