Способ обеспечения целостности передаваемой информации

Изобретение относится к области исправления ошибок на приемной стороне в системах связи. Техническим результатом является повышение эффективности приема передаваемой информации при учете вероятности модификации передаваемой информации. Способ обеспечения целостности передаваемой информации состоит в том, что на приемной стороне принимают информацию по n параллельным каналам, вычисляют значение , где P(S₁) и P(S₂) - априорные вероятности передаваемых символов (S₁=1; S₂=-1) - информации от источника; x₁, …, x_i, …, x_n значения принятых символов по каждому из n каналов; вероятность несанкционированного воздействия третьим лицом на передаваемые символы от источника в каждом i-м из n каналов; сравнивают вычисленное значение с нулем; если вычисленное значение больше нуля, то принимают решение, что передавался символ S₁, иначе передавался символ S₂. 9 ил., 1 табл.

 

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

Известные способы для обеспечения безошибочного приема передаваемой информации [1] используют механизмы перемежения, хоппинга, добавления избыточности в передаваемый сигнал, использования обратной связи. При этом происходит только контроль целостности информации и в том случае, если ее во время передачи несанкционированно изменили, потребуется повторная передача данных.

Главным недостатком известных способов является увеличение времени задержки передачи информации, обусловленное применением перемежения, хоппинга, использованием обратной связи для повторной передачи информации в случае больших показателей вероятностей изменения информации во время передачи по линиям связи третьими лицами. Таким образом, величина задержки передачи информации может быть существенно выше нормативных показателей предоставления мультимедийных высокоскоростных услуг, вследствие чего известные способы могут ограниченно использоваться для приложений, функционирующих в реальном масштабе времени (критичных к временным задержкам).

При применении способов перемежения предварительно необходимо оценивать глубину перемежения при данных параметрах канала для достижения наибольшей относительной скорости передачи информации. Таким образом, информация по каналу передается с задержкой, зависящей от метода перемежения, применяемого на передающей стороне, также стоит учесть необходимость деперемежения на приемной стороне, что также вызывает временную задержку, обусловленную необходимостью получения символов для восстановления исходной последовательности.

В свою очередь применение хоппинга необходимо для борьбы с замираниями и не всегда дает выигрыш в скорости. Для данного способа необходимо иметь не менее одного канала в резерве для реализации хоппинга. Таким образом, возможен вариант, что резервные каналы будут простаивать и использоваться лишь в моменты, когда в основном канале передачи информации появляются ошибки, что в свою очередь не эффективно с точки зрения использования ресурсов.

Использование метода обратной связи также вносит временную задержку, необходимую на переспрос со стороны приемника в случае принятия комбинации с ошибками. Кроме того, для организации обратной связи необходим обратный канал для возможности посылки передатчику сигнала о необходимости повторной отправки кодовой комбинации. Таким образом, время передачи информации за счет ее повторной передачи увеличивается вдвое.

Наиболее близким техническим решением по отношению к заявляемому изобретению являются методы параллельной передачи информации в сетях связи [2, прототип].

Недостатком известного прототипа [2] является то, что в нем не учтены вероятности модификации передаваемой информации третьими лицами (несанкционированно действующим лицом) на протяжении всей передачи от отправителя до получателя по параллельным каналам.

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

Поставленная цель достигается тем, что информационные символы (условно «0» и «1») передаются одновременно непараллельным каналам, на приемной стороне они поступают в решающую схему, в которой на основе принятых информационных символов, знаний о величинах вероятностей модификации передаваемой информации третьими лицами (на каждом параллельном соединении), априорных вероятностей передаваемых символов, вычисляется некоторое значение, в том случае, если оно больше нуля передавался один символ (условно «0»), в противном случае передавался другой (условно «1»).

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

Сущность изобретения поясняется нижеследующим описанием и приложенными к нему чертежами, где на Фиг.1 приведена функциональная схема предлагаемого способа обеспечения целостности передаваемой информации, на Фиг.2-5 приведен алгоритм, реализующий предлагаемый способ обеспечения целостности передаваемой информации, на Фиг.6-9 представлены графики, полученные с помощью имитационного моделирования, подтверждающие работоспособность заявленного способа обеспечения целостности передаваемой информации.

Информационный поток от источника, состоит из символов S₁ или S₂, с априорными вероятностями появления Р(S₁) и Р(S₂) соответственно. Такой поток передается одновременно по совокупности параллельных n каналов, где на передаваемые по линиям связи символы могут несанкционированно воздействовать третьи лица с вероятностью $$P_M^i$$ , на каждом i-м соединении из совокупности $$\left(i=\overline{\mathrm{0,}n}\right)$$ .

На приемной стороне принятые символы x=(х₁,…,x_i…,x_n) поступают в предлагаемую решающую схему, соответственно по параллельным n входам.

Таким образом, условная вероятность того, что решение на выходе решающей схемы с n входами будет принято в пользу S₁ или S₂, будет определяться формулами:

$$P\left(S_1/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)=\frac{P\left(S_1\right)\left\{\underset{i\in x_i=S_1}{П}\left(1-P_M^{\left(i\right)}\right)\underset{i\in x_i=S_2}{П}{P}_M^{\left(i\right)}\right\}}{P\left(x_i;i=\overline{\mathrm{0,}n}\right)};$$

$$P\left(S_2/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)=\frac{P\left(S_2\right)\left\{\underset{i\in x_i=S_1}{П}{P}_M^{\left(i\right)}\underset{i\in x_i=S_2}{П}\left(1-P_M^{\left(i\right)}\right)\right\}}{P\left(x_i;i=\overline{\mathrm{0,}n}\right)};$$

Однако, так как значение вероятности в знаменателе неизвестно, возьмем отношение вероятностей, и, если результат окажется больше единицы, решение будет принято в пользу S₁, иначе S₂:

$$\frac{P\left(S_1/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}{P\left(S_2/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}=\frac{P\left(S_1\right)}{P\left(S_2\right)}\times \frac{\underset{i\in x_i=S_1}{П}\left(1-P_M^{\left(i\right)}\right)}{\underset{i\in x_i=S_1}{П}P\left({}_M^{\left(i\right)}\right)}\times \frac{\underset{i\in x_i=S_2}{П}{P}_M^{\left(i\right)}}{\underset{i\in x_i=S_2}{П}\left(1-P_M^{\left(i\right)}\right)},$$

Прологарифмировав обе части выражения, получаем:

$$ln\frac{P\left(S_1/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}{P\left(S_2/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}=ln\frac{P\left(S_1\right)}{P\left(S_2\right)}+{\displaystyle \sum _{i\in x_i=S_1}ln\frac{\left(1-P_M^{\left(i\right)}\right)}{P_M^{\left(i\right)}}+{\displaystyle \sum _{i\in x_i=S_2}\frac{P_M^{\left(i\right)}}{\left(1-P_M^{\left(i\right)}\right)}}}.$$

Введем следующие обозначения:

$$a_0=ln\frac{P\left(S_1\right)}{P\left(S_2\right)};\left(\text{1}\right)$$

$$a_i=ln\frac{\left(1-P_M^{\left(i\right)}\right)}{P_M^{\left(i\right)}};\left(\text{2}\right)$$

Условно S₁=+1,S₁=-1, в результате преобразовании получили:

$$ln\frac{P\left(S_1/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}{P\left(S_2/\left(x_i;i=\overline{\mathrm{0,}n}\right)\right)}=a_0+{\displaystyle \sum _{i=0}^n{x}_i{a}_i}.$$

Таким образом, можно утверждать, что для решающей схемы с n параллельными входами, одновременно принятыми по ним сообщениями x=(х₁,…,x_i,…,x_n) и одним выходом имеет место следующее соотношение:

$$a_0+{\displaystyle \sum _{i=0}^n{x}_i{a}_i}=\{\begin{array}{l}>\mathrm{0,}то{\text{ S}}^{\text{*}}=S_1,\hfill \\ <\mathrm{0,}то{\text{ S}}^{\text{*}}=S_2.\hfill \end{array}\left(\text{3}\right)$$

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

Предлагаемое изобретение поясняется конкретным примером реализации в виде устройства, приведенного на Фиг.1.

Устройство содержит:

1 - параллельные входы устройства,

2 - блок суммирования произведений,

3 - блок вычисления коэффициентов a_i, (в соответствии с формулой (2)),

4 - блок сумматора,

5 - блок вычисления коэффициентов a₀ (в соответствии с формулой (1)),

6 - выход устройства.

Устройство работает следующим образом.

В блок 2 поступают:

- из 1 по каждому параллельному входу сигнал x=(x₁,…,x_i,…,x_n), измененный несанкционированно действующим лицом с вероятностью $$P_M^{\left(i\right)}\left(i=\overline{\mathrm{0,}n}\right)$$ , принятый по i-му параллельному каналу,

- значение аi, вычисленное в блоке 2.

Затем в блоке 2 происходит перемножение поступивших величин с входов и значения с блока 3 и последующее их суммирование в соответствии с правым слагаемым левой части равенства (3).

В блоке 3 вычисляются значения коэффициентов a_i в соответствии с формулой (2).

В блоке 5 вычисляются значения коэффициентов a₀ (в соответствии с формулой (1)).

Далее в блоке 4 происходит суммирование поступивших в него величин и сравнивание с нулем получившейся. В том случае, если значение больше нуля, решение о переданном символе принимается в пользу символа S₁, иначе S₂.

На выходе устройства (блок 6) символ, переданный источником.

Таким образом, использование новых приемов (работа решающей схемы на приеме) позволяет сократить время передачи информации из-за отсутствия запросов на повторную передачу и использования методов перемежения и хоппинга, а также учитывает вероятность изменения информации третьи лица во время передачи по параллельным каналам.

Для проверки изобретения было проведено имитационное моделирование функционирования решающей схемы (PC).

Учитывая, что результаты будут иметь стохастический характер, использовали метод Монте-Карло [3].

Приняты были следующие допущения для ожидаемых результатов:

- точность ε=0,01,

- достоверность α=0,999.

Для определения достаточного количества испытаний N, при статистическом моделировании, использовали выражение из [3]:

$$N=t_{\alpha }^2\frac{p\left(1-p\right)}{{\epsilon }^2},\left(\text{4}\right)$$

где t_α ^- функция, обратная нормальному распределению (при α=0,999 t_α=3,29), p - искомая вероятность обеспечения целостности информации.

Из (4) видно, что максимума значение N достигнет при p=0,5, окончательно получили:

$$N={\mathrm{3,29}}^2\left(\frac{\mathrm{0,5}\left(1-\mathrm{0,5}\right)}{{\mathrm{0,01}}^2}\right)=27061$$ .

Таким образом, полагая общее количество испытаний N=30000 при заданных параметрах, будет обеспечена абсолютная погрешность результатов не ниже 1%.

Этапы работы алгоритма (Фиг.2-5).

1. Ввод входных данных (блок 1-2):

- вероятность модификации $${Р}_{м}={Р}_{м}^{\left(j\right)}$$ ( $$j=\overline{\mathrm{1,}n}$$ , где n - количество параллельных соединений),

- априорная вероятность P(S₁) появления символа S₁,

- количество испытаний N=30000,

- максимальное количество параллельных соединений n=15.

2. Моделирование передаваемого потока сообщений S осуществляется по правилу (блок 4-8):

$$S=\{\begin{array}{l}{S}_i=+\mathrm{1,}\text{ если z}\le \text{P}\left({\text{S}}_{\text{1}}\right)\hfill \\ S_i=-\mathrm{1,}\text{ если z}>\text{P}\left({\text{S}}_{\text{1}}\right)\hfill \end{array}$$ ,

где z - случайное число, генерируемое с помощью датчика случайных чисел в соответствии с равномерным законом распределения (0≤z≤1), $$i=\overline{\mathrm{1,}N}$$ .

3. Формирование потока x_ij, состоящего из N измененных (под действием Р_м) символов потока S_i, переданных по n параллельным соединениям, выполняется по правилу (блок 10-15):

$$x_{ij}=\{\begin{array}{c}если\text{ z}\le {\text{P}}_{\text{м}},тоизменениеесть{\text{, x}}_{\text{ij}}=S_i\times \left(-1\right)\\ если\text{ z}>{\text{P}}_{\text{м}},тоизменениянет,{\text{x}}_{\text{ij}}=S_i\end{array}$$ ,

где z - случайное число, генерируемое с помощью датчика случайных чисел в соответствии с равномерным законом распределения (0≤z≤1), $$i=\overline{\mathrm{1,}N}$$ , $$j=\overline{\mathrm{1,}n}$$ .

4. Вычисление коэффициентов a₀ и a_j соответственно (блок 16-18):

$$a_0=ln\frac{P\left(S_1\right)}{1-P\left(S_1\right)},$$ $$a_j=ln\frac{\left(1-P_{м}\right)}{P_{м}},$$

где $$j=\overline{\mathrm{1,}n}$$ .

5. Вычисление соотношения (3) для i-го символа переданного по j-соединениям (блок 20-26):

$$X_{ij}=a_0+{\displaystyle \sum _{j=1}^n{x}_{ij}{a}_j}$$ ,

где $$i=\overline{\mathrm{1,}N}$$ , j=3,5,…,n.

6. Формирование потока принятых символов S^*=y_ij (блок 27-29):

$$y_{ij}=\{\begin{array}{l}{y}_{ij}=+\mathrm{1,}{\text{ если X}}_{\text{ij}}>0\hfill \\ y_{ij}=-\mathrm{1,}{\text{ если X}}_{\text{ij}}<0\hfill \end{array}$$ ,

где $$i=\overline{\mathrm{1,}N}$$ , j=3,5,…,n.

7. Подсчет верно принятых символов и вычисление вероятности целостности информации на выходе решающей схемы Р_{Ц РС} (блок 33-38):

$$P_{ц\text{ РУ i}}=\frac{N_{al}}{N}$$ ,

где N_al - количество верно принятых символов при передаче по i-соединениям, i=3,5,…,n.

8. Подсчет верно принятых символов и вычисление вероятности целостности информации без использования совокупности параллельных соединений (блок 40-43):

$$P^{ц}=\frac{N_p}{N}$$ ,

где N_p - количество верно принятых символов при передаче по одному соединению (n=1).

Программная реализация изобретения была выполнена в среде MatLab. Результаты имитационного моделирования представлены на Фиг.6 и в таблице 1, где n - количество параллельных соединений для передачи информации (или число входов решающей схемы), Р_м - вероятность модификации сообщения, Р_{ц РС} - вероятность обеспечения целостности сообщения на выходе РС.

Таблица 1 - Зависимость РцРС=ƒ(Рм) при различном количестве входов РС
n Рм	Рц РС
3	5	7	9	11	13	15
0,05	0,9922	0,9988	0,9996	0,9999	1	1	1
0,1	0,9720	0,9920	0,9976	0,9992	0,9997	0,9999	1
0,15	0,9390	0,9729	0,9889	0,9945	0,9974	0,9990	0,9996
0,2	0,8944	0,9412	0,9655	0,9793	0,9866	0,9919	0,9955
0,25	0,8421	0,8965	0,9298	0,9507	0,9652	0,9762	0,9825
0,3	0,7836	0,8366	0,8735	0,9020	0,9217	0,9374	0,9509
0,35	0,7159	0,7673	0,8026	0,8297	0,8530	0,8716	0,8894
0,4	0,6515	0,6866	0,7114	0,7329	0,7523	0,7886	0,7853
0,45	0,5765	0,5952	0,6125	0,6254	0,6380	0,6476	0,6577
0,5	0,4959	0,4959	0,4959	0,4959	0,4959	0,4959	0,4959
0,55	0,5722	0,5935	0,6105	0,6246	0,6376	0,6494	0,6539
0,6	0,6512	0,6845	0,7073	0,7323	0,7517	0,7692	0,7852
0,65	0,7125	0,7615	0,7950	0,8252	0,8474	0,8666	0,8841
0,7	0,7817	0,8359	0,8734	0,9005	0,9222	0,9386	0,9507
0,75	0,8414	0,8952	0,9297	0,9518	0,9670	0,9770	0,9835
0,8	0,8969	0,9427	0,9689	0,9810	0,9887	0,9936	0,9962
0,85	0,9416	0,9739	0,9880	0,9943	0,9970	0,9987	0,9994
0,9	0,9736	0,9916	0,9973	0,9993	0,9998	0,9999	1
0,95	0,9932	0,9986	0,9998	1	1	1	1
1	1	1	1	1	1	1	1

На Фиг.6 представлен характер зависимости Р_{ц РС}=ƒ(Р_м) при n=3,7, 11, 15.

По полученным результатам имитационного моделирования можно сделать следующие выводы:

- теоретические результаты, полученные с помощью (3), совпадают с результатами моделирования,

- работоспособность алгоритма принятия решения о восстановлении модифицированного переданного символа подтверждена,

- при увеличении вероятности модификации Р_м алгоритм позволяет увеличивать вероятность обеспечения целостности информации Р_рез ^ц за счет коэффициентов а, с точкой излома в Р_м=Р_{ц РС}=0,5.

Так как в выражение для вычисления a_i входит вероятность модификации сообщения Р_м, которая имеет случайный характер, то можно предположить, что точность ее определения будет влиять на результаты моделирования в целом. В этой связи, был проведен с помощью статистического моделирования анализ влияния точности Р_м на принятие решения о передаваемом символе.

Результаты моделирования представлены на Фиг.7-9 при n=5 и Р(S₁)=Р(S₂)=0,5.

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

1. Мелентьев О.Г. Теоретические аспекты передачи данных по каналам с группирующимися ошибками / Под редакцией профессора Шувалова В.П. - М.: Горячая линия - Телеком, 2007. - 232 с.

2. Андронов И.С.Передача дискретных сообщений по параллельным каналам / И.С.Андронов, Л.М. Финк / - М.: Сов. радио, 1971. - 408 с.(прототип).

3. Бусленко Н.П. Моделирование сложных систем / Н.П.Бусленко / - М.: Наука, 1968. - 356 с.

Способ обеспечения целостности передаваемой информации отличающийся тем, что на приемной стороне принимают информацию по n параллельным каналам, вычисляют значение , где P(S₁) и P(S₂) - априорные вероятности передаваемых символов (S₁=1; S₂=-1) информации от источника; x₁, …, x_i, …, x_n - значения принятых символов по каждому из n каналов; вероятность несанкционированного воздействия третьим лицом на передаваемые символы от источника в каждом i-м из n каналов; сравнивают вычисленное значение с нулем; если вычисленное значение больше нуля, то принимают решение, что передавался символ S₁, иначе передавался символ S₂.