Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом

Исследована эффективность случайного кодирования при многократной передаче безизбыточных сообщений по двоичному симметричному каналу связи с отводом. Получены неасимптотические оценки надежности восстановления сообщений законным получателем информации и стойкости их защиты в отводном канале. Дослідж...

Full description

Saved in:

Bibliographic Details
Published in:	Системні дослідження та інформаційні технології
Date:	2011
Main Authors:	Алексейчук, А.Н., Гришаков, С.В.
Format:	Article
Language:	Russian
Published:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2011
Subjects:	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/50126
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом / А.Н. Алексейчук, С.В. Гришаков // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 37-47. — Бібліогр.: 17 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-50126
record_format	dspace
spelling	Алексейчук, А.Н. Гришаков, С.В. 2013-10-05T19:44:25Z 2013-10-05T19:44:25Z 2011 Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом / А.Н. Алексейчук, С.В. Гришаков // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 37-47. — Бібліогр.: 17 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50126 621.391:519.2 Исследована эффективность случайного кодирования при многократной передаче безизбыточных сообщений по двоичному симметричному каналу связи с отводом. Получены неасимптотические оценки надежности восстановления сообщений законным получателем информации и стойкости их защиты в отводном канале. Досліджено ефективність випадкового кодування під час багаторазової передачі безнадлишкових повідомлень двійковим симетричним каналом зв’язку з відводом. Отримано неасимптотичні оцінки надійності відновлення повідомлень законним одержувачем інформації та стійкості їх захисту у відвідному каналі. The efficiency of random coding during the multiple irredundant messages transmission through a binary symmetric channel with take-off is investigated. Unasymptotic estimates of the reliability of message recovery by a legitimate recipient of information and the sustainability of their protection in take-out channel are obtained. ru Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом Неасимптотичні оцінки ефективності випадкового кодування в системі передачі інформації двійковим симетричним каналом зв’язку з відводом Unasymptotic estimates of random coding efficiency in the system of information transfer channel with take-off Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
spellingShingle	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом Алексейчук, А.Н. Гришаков, С.В. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
title_short	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
title_full	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
title_fullStr	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
title_full_unstemmed	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
title_sort	неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом
author	Алексейчук, А.Н. Гришаков, С.В.
author_facet	Алексейчук, А.Н. Гришаков, С.В.
topic	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
topic_facet	Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи
publishDate	2011
language	Russian
container_title	Системні дослідження та інформаційні технології
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
format	Article
title_alt	Неасимптотичні оцінки ефективності випадкового кодування в системі передачі інформації двійковим симетричним каналом зв’язку з відводом Unasymptotic estimates of random coding efficiency in the system of information transfer channel with take-off
description	Исследована эффективность случайного кодирования при многократной передаче безизбыточных сообщений по двоичному симметричному каналу связи с отводом. Получены неасимптотические оценки надежности восстановления сообщений законным получателем информации и стойкости их защиты в отводном канале. Досліджено ефективність випадкового кодування під час багаторазової передачі безнадлишкових повідомлень двійковим симетричним каналом зв’язку з відводом. Отримано неасимптотичні оцінки надійності відновлення повідомлень законним одержувачем інформації та стійкості їх захисту у відвідному каналі. The efficiency of random coding during the multiple irredundant messages transmission through a binary symmetric channel with take-off is investigated. Unasymptotic estimates of the reliability of message recovery by a legitimate recipient of information and the sustainability of their protection in take-out channel are obtained.
issn	1681–6048
url	https://nasplib.isofts.kiev.ua/handle/123456789/50126
citation_txt	Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом / А.Н. Алексейчук, С.В. Гришаков // Систем. дослідж. та інформ. технології. — 2011. — № 4. — С. 37-47. — Бібліогр.: 17 назв. — рос.
work_keys_str_mv	AT alekseičukan neasimptotičeskieocenkieffektivnostislučainogokodirovaniâvsistemeperedačiinformaciipodvoičnomusimmetričnomukanalusvâzisotvodom AT grišakovsv neasimptotičeskieocenkieffektivnostislučainogokodirovaniâvsistemeperedačiinformaciipodvoičnomusimmetričnomukanalusvâzisotvodom AT alekseičukan neasimptotičníocínkiefektivnostívipadkovogokoduvannâvsistemíperedačíínformacíídvíikovimsimetričnimkanalomzvâzkuzvídvodom AT grišakovsv neasimptotičníocínkiefektivnostívipadkovogokoduvannâvsistemíperedačíínformacíídvíikovimsimetričnimkanalomzvâzkuzvídvodom AT alekseičukan unasymptoticestimatesofrandomcodingefficiencyinthesystemofinformationtransferchannelwithtakeoff AT grišakovsv unasymptoticestimatesofrandomcodingefficiencyinthesystemofinformationtransferchannelwithtakeoff
first_indexed	2025-11-26T07:32:18Z
last_indexed	2025-11-26T07:32:18Z
_version_	1850617388064571392
fulltext	© А.Н. Алексейчук, С.В. Гришаков, 2011 Системні дослідження та інформаційні технології, 2011, № 4 37 УДК 621.391:519.2 НЕАСИМПТОТИЧЕСКИЕ ОЦЕНКИ ЭФФЕКТИВНОСТИ СЛУЧАЙНОГО КОДИРОВАНИЯ В СИСТЕМЕ ПЕРЕДАЧИ ИНФОРМАЦИИ ПО ДВОИЧНОМУ СИММЕТРИЧНОМУ КАНАЛУ СВЯЗИ С ОТВОДОМ А.Н. АЛЕКСЕЙЧУК, С.В. ГРИШАКОВ Исследована эффективность случайного кодирования при многократной пере- даче безизбыточных сообщений по двоичному симметричному каналу связи с отводом. Получены неасимптотические оценки надежности восстановления сообщений законным получателем информации и стойкости их защиты в от- водном канале. ВВЕДЕНИЕ Математическая модель системы передачи информации по каналу связи с отводом предложена в [1] и в дальнейшем изучалась в [2–11] и ряде других работ. В настоящее время эта модель широко используется при разработке алгоритмических методов защиты информации от утечки по побочным ка- налам связи, квантово-криптографических протоколов распределения клю- чей, схем разделения секрета, а также при решении других криптографиче- ских задач [10, 11]. Традиционная система передачи информации по каналу связи с отво- дом состоит из двух статистически независимых каналов связи с общим входом. Выход одного (основного) канала наблюдает законный получатель, а выход другого (отводного) канала — противник. Для повышения стойкости защиты информации в отводном канале применяют случайное кодирование, при котором входные сообщения преобразуются в дискретные сигналы, вы- бираемые случайно и равновероятно из подходящих конечных множеств. В большинстве доступных публикаций, посвященных исследованию эффек- тивности случайного кодирования, рассматривается случай, в котором ос- новной канал связи является идеальным (не имеет помех), а отводной — двоичным симметричным каналом или каналом со стиранием [3, 5–11]. В частности, в [8, 9] были исследованы асимптотические свойства характе- ристик эффективности случайного кодирования при многократной передаче безизбыточного случайного сообщения по идеальному основному и двоич- ному симметричному отводному каналам связи, а также получены асимпто- тические оценки минимального количества передач, необходимого для восстановления противником переданного сообщения с заданной надеж- ностью. Вместе с тем, асимптотический вид оценок, полученных в [8, 9], не позволяет применять их непосредственно к системам со случайным кодиро- ванием кодами фиксированной длины. А.Н. Алексейчук, С.В. Гришаков ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 38 Цель работы — исследовать эффективность случайного кодирования при многократной передаче сообщений по неидеальному основному каналу связи. В работе получены неасимптотические оценки вероятности правиль- ного восстановления сообщений законным получателем и, соответственно, противником. Показано, что при определенных соотношениях между па- раметрами линейных кодов, применяемых для случайного кодирования, и вероятностями искажений в основном и отводном каналах можно обеспе- чить надежный прием сообщений законным получателем при высокой прак- тической стойкости их защиты в отводе, используя сравнительно небольшое число передач. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ РЕЗУЛЬТАТЫ Рассмотрим систему передачи информации по каналу связи с отводом, со- стоящую из источника и двух статистически независимых каналов связи с общим входом: основного канала — от источника к законному получателю, и отводного канала — от источника к противнику [1, 2]. Предположим, что основной канал является двоичным симметричным каналом с вероятностью ошибки 1p , а отводной — двоичным симметричным каналом с вероятно- стью ошибки 2p , где 5,00 21 <<< pp . Источник вырабатывает случайное сообщение S с равномерным распределением на множестве k kV }1,0{= , для передачи которого отправитель выбирает сюръективное линейное отображение kn VV →:σ и генерирует t независимых случайных векторов tXX ..., ,1 с равномерным распределением на множестве )(1 sCs −= σ , где kVs∈ — значение случайного вектора S . Затем последовательность tXX ..., ,1 передается по основному и отводному каналам связи. При этом она искажается и в основном канале преобразовывается в случайную после- довательность tYY ..., ,1 , а в отводном канале — в случайную последователь- ность tZ Z..., ,1 . Необходимо получить оценки вероятности правильного восстановления сообщения S по каждой из указанных последовательностей в предположении, что декодеры основного и отводного каналов строятся на основе тех или иных практически реализуемых алгоритмов. Предположим, что законный получатель информации применяет сле- дующий алгоритм декодирования по методу максимума правдоподобия. Алгоритм 1. Пусть tyyy ..., ,1= — наблюдаемая реализация случайной последовательности tYY ..., ,1 . Тогда получатель находит последовательность )(,...),()( 1 tyyy σσσ = и выбирает в качестве оценки искомого значения случайного вектора S произвольный элемент )(** yss = с наибольшей час- тотой встречаемости в последовательности )(yσ . Если противнику известен некоторый критерий отбраковки ложных значений сообщения S (например, S является ключом симметричной крип- тосистемы, и существует возможность его опробования), то алгоритм 1 можно модифицировать следующим образом. Неасимптотические оценки эффективности случайного кодирования в системе передачи … Системні дослідження та інформаційні технології, 2011, № 4 39 Алгоритм 2. Пусть tzzz ..., ,1= — наблюдаемая реализация случайной последовательности tZ Z..., ,1 . Тогда противник находит последователь- ность )(),...,()( 1 tzzz σσσ = , составляет список ее членов, расположенных в порядке убывания их частот, и опробует в указанном порядке (до первого успеха) векторы из списка. Обозначим ),( 111 ptλλ = и ),( 222 ptλλ = вероятности правильного восстановления сообщения S с использованием алгоритмов 1 и 2 соответ- ственно. Для того, чтобы привести оценки параметров 1λ , 2λ , введем ряд дополнительных обозначений. Обозначим C линейный ),( knn − -код, равный ядру отображения σ . Для любого ]1,0[∈p положим \|\|\|\|\|\|\|\| )1();( un Cu u s s pppC − ∈ ∑ −=π , (1) где )(1 sCs −= σ — смежный класс (СК) кода C , соответствующий вектору kVs∈ ; );();( 00 pCpC ππ = , }}0{\:);({max);(1 ks VspCpC ∈= ππ . (2) Отметим, что на основании тождества Мак-Вильямс [12] ∆−= ∑ ⊥∈ − \|\|\|\|)1(2);( u u auk s C pCπ , kVs∈ , (3) где ⊥C — код, дуальный к ;C a — произвольный вектор, принадлежащий СК sC ; au — булево скалярное произведение векторов nVua ∈, , p21−=∆ . Отсюда непосредственно следует, что );();( 01 pCpC ππ < для любого 5,00 << p . Утверждение 1. Справедливы неравенства ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ −−−≥ 2 111011 ));();(( 2 exp21),( pCpCtpt k ππλ , (4) tpCpt ));(1(1),( 2022 πλ −−≤ . (5) Доказательство. Как следует из описания алгоритма 2, вероятность его успешного завершения не превосходит вероятности события, состоящего в том, что случайный вектор S присутствует в последовательности ).(Zσ Последнее равносильно тому, что хотя бы один из векторов искажений, пе- реводящих слово iX в слово iZ в отводном канале, принадлежит коду ,C ti ,1= . Отсюда вытекает справедливость неравенства (5). Докажем неравенство (4). Обозначим sP условное распределение веро- ятностей на множестве значений случайной последовательности tYYY ..., ,1= при условии sS = ; )(Yns — частоту появления вектора s в последовательности )(Yσ . Справедливо равенство А.Н. Алексейчук, С.В. Гришаков ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 40 ∑ ∈ − == kVs s k sYsPpt })({2),( 11λ . (6) Заметим теперь, что для любого kVs∈ событие })({ sYs ≠ влечет со- бытие ∪ ss ss YnYn ≠′ ′ > )}()({ . Следовательно, для любого 0>A выполняются следующие неравенства: ≤⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ >≤≠ ≠′ ∪ ss ssss YnYnPsYsP )}()({})({ ' ∑ ≠′ ′ >+≤≤ ss ssss AYnPAYnP })({})({ . (7) Далее, при выполнении условия sS = случайная величина )(Yns имеет биномиальное распределение с параметрами )),;(,( 10 pCt π а случай- ная величина )(Yns′ — биномиальное распределение с параметрами ));(,( 1pCt ss ′⊕π . Следовательно, в силу неравенств для вероятностей боль- ших уклонений [13] при выполнении условия );();( 10 1 11 pCAtpC ππ << − (8) для любых kVss ∈′, , ss ≠′ , справедливы следующие неравенства: }));((2{exp})({ 2 10 1 pCAttAYnP ss π−−≤≤ − , (9) }));((2{exp})({ 2 1 1 pCAttAYnP ssss ′⊕ − ′ −−≤> π . (10) Подставляя оценки (9), (10) в формулу (7) и принимая во внимание второе соотношение (2), получим, что при выполнении условия (8) +−−≤≠ − }));((2{exp})({ 2 10 1 pCAttsYsPs π }));((2{exp)12( 2 11 1 pCAttk π−−−+ − . (11) Наконец, полагая в формуле (11) )),;();(( 2 1 1110 1 pCpCAt ππ +=− на ос- новании равенства (6) получим соотношение ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − −−≥ 2 1110 11 2 );();( 2exp21),( pCpC tpt k ππ λ , которое равносильно неравенству (4). Утверждение доказано. Отметим, что соотношения (4), (5) справедливы для любого линейного ),( knn − -кода .C Чтобы оценивать с их помощью эффективность систем со случайным кодированием, построенных на основе конкретных кодов, необ- ходимо иметь пригодные для практических вычислений границы парамет- Неасимптотические оценки эффективности случайного кодирования в системе передачи … Системні дослідження та інформаційні технології, 2011, № 4 41 ров (2). Ряд таких границ, вытекающих, в основном, из результатов работ [7, 14–16], содержит следующее утверждение. Утверждение 2. Пусть C — произвольный линейный ),( knn − -код с минимальным расстоянием d и дуальным расстоянием d ′ . Тогда для лю- бого 5,00 << p справедливы следующие неравенства: ))12(1(2);(0 dkkpC ′− ∆−+≤π , (12) p kp pC − − ≤ 1 0 2);(π , (13) ini n li nk pp i n l ln ppC − += − −− −⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ +⎥⎥ ⎤ ⎢⎢ ⎡ −+≤ ∑ )~1(~ 2)~1(2);( 12 1 0π , (14) где p21−=∆ , ⎥⎦ ⎥ ⎢⎣ ⎢ − = 2 1'dl , )1(2 21~ p pp − − = . (15) Кроме того, справедливо неравенство 1 )1(2);();( 1 1 10 +− +− ∆+ ∆ −≥− kn kn nppCpC ππ , (16) а при условии 3≥d — неравенство 2 1 10 );();( + ∆≥− n pCpC ππ . (17) Обе границы (12), (17) достигаются, если C является кодом Хэмминга. Доказательство. Справедливость оценки (12) и ее достижимость для кодов Хэмминга доказаны в [7]. Неравенство (13) следует из формулы )()1();( но0 CPppC n +−=π , (18) где ∑ ∈ −−= }0{\ \|\|\|\|\|\|\|\| но )1();( Cx xnx pppCP (19) есть вероятность необнаружения ошибки кодом C , и соотношения ( ) np p n pCpCP )1(\|\|2);( 1но −−≤ −− , полученного в работе [16]. Для доказательства формулы (14) воспользуемся неравенством [15] ini n li pp i n l ln pGP − += − −⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ +⎥⎥ ⎤ ⎢⎢ ⎡ ≤ ∑ )~1(~ 2)~;( 12 1 но , 5,0~0 << p (20) справедливым для любого двоичного линейного кода G длины n , исправ- ляющего l ошибок. Полагая в формуле (20) ,⊥=CG при выполнении (15) получим следующее неравенство: А.Н. Алексейчук, С.В. Гришаков ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 42 ini n li pp i n l ln pCP − += − ⊥ −⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ +⎥⎥ ⎤ ⎢⎢ ⎡ ≤ ∑ )~1(~ 2)~;( 12 1 но . (21) Далее, согласно формуле (3) при ,0=s выполняется равенство =);(0 pCπ ∑ ⊥∈ − ∆= Cx xk \|\|\|\|2 . Следовательно, ∑∑ ⊥⊥ ∈ − ∈ − =⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − +=∆+= }0{\ \|\|\|\| }0{\ \|\|\|\| 0 ~1 ~ 22);( Cx x k Cx xk p ppCπ )~;()~1(2)~1(~)~1(2 но \|\|\|\|\|\|\|\| }0{\ pCPpppp nkxnx Cx nk ⊥−−− ∈ −− −+=−−+= ∑ ⊥ . (22) Подставляя оценку (21) в формулу (22), получим неравенство (14). Для доказательства неравенства (16) воспользуемся следующей оцен- кой [14]: 1 1 1 0 1 1 );( );( +− +− ∆− ∆+ ≥ kn kn pC pC π π . (23) На основании (23) справедливы соотношения 1 );(2 1 11);();();( 1 1 01 1 010 +− +− +− +− ∆+ ∆ =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∆+ ∆− −≥− kn kn kn kn pCpCpCpC ππππ , из которых в силу неравенства nppC )1();(0 −≥π , вытекающего из форму- лы (18), следует оценка (16). Убедимся, наконец, в справедливости неравенства (17). Зафиксируем элемент kVs∈ такой, что );();(1 pCpC sππ = , и вектор sCa∈ . Обозначим ⊥= CG , }0:{0 =∈= uaGuG , }1:{1 =∈= uaGuG . На основании формулы (3) и неравенства между средним арифметиче- ским и средним геометрическим справедливы соотношения =∆−−∆=− ∑∑ ∈ − ∈ − Gu uauk Gu ukpCpC \|\|\|\|\|\|\|\| 10 )1(22);();( ππ ∑ ∈ −− ∆≥∆= ∑ ∈ −− 1 )1( 1 \|\|\|\|2 \|\|\|\|)1(2 Gu k u Gu uk . Следовательно, для обоснования оценки (17) достаточно показать, что при 3≥d выполняется следующее неравенство: 2 1\|\|\|\|2 1 )1( + ≤∑ ∈ −− nu Gu k . (24) Неасимптотические оценки эффективности случайного кодирования в системе передачи … Системні дослідження та інформаційні технології, 2011, № 4 43 Для любого },,{ 10 GGGH ∈ обозначим ∈== ),...,({\|)( 1 ni uuuHs \|}1: =∈ iuH , ni ,1= . Заметим, что ∑∑ = −− ∈ −− = n i i k Gx k Gsu 1 1 )1()1( )(2\|\|\|\|2 1 . (25) При этом, поскольку G и 0G являются линейными кодами размер- ности k и 1−k соответственно, а 1G — смежным классом кода 0G , то }2 ,0{)( 1−∈ k i Gs , }2 ,0{)( 2 0 −∈ k i Gs , }2 ,2 ,0{)( 12 1 −−∈ kk i Gs , ni ,1= . (26) Предположим, что существует два различных значения },...,2,1{ , nji ∈ таких, что 1 11 2)()( −== k ji GsGs . Тогда =)( 0Gsi 0)( 0 == Gs j , согласно первым двум соотношениям (26). Следовательно, для любого слова Guuu n ∈= ),...,( 1 выполняется равенство ji uu = . Но в таком случае дуальное расстояние кода G (равное минимальному рас- стоянию d кода ⊥= GC ) не превосходит 2, что противоречит условию утверждения. Итак, существует не более одного значения }...,,2,1{ ni∈ , для кото- рого 1 1 2)( −= k i Gs . Для остальных же значений ij ≠ в силу третьего соот- ношения (26) 2)( 2 1 −≤ k j Gs . Отсюда следует, что ≤∑ = −− n i i k Gs 1 )1( )(2 2 1))1(22(2 21)1( + =−+≤ −−−− nnkkk , из чего следует, что на основании форму- лы (25) справедливо неравенство (24), что и требовалось доказать. Достижимость оценки (17) для ),( knn − -кода Хэмминга C , 12 −= kn , вытекает из следующих равенств [3]: ))12(1(2);( 12 0 − ∆−+= − kkkpCπ , )1(2);( 12 1 − ∆−= − kkpCπ . Утверждение доказано. ЧИСЛЕННЫЕ ОЦЕНКИ ХАРАКТЕРИСТИК ЭФФЕКТИВНОСТИ СИСТЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ ПО КАНАЛУ СВЯЗИ С ОТВОДОМ Для сравнения полученных оценок были проведены численные расчеты значений в правых частях неравенств (12)–(14), (16), (17). Расчеты проводи- лись для различных линейных кодов ,C имеющих длину от нескольких де- сятков до нескольких сотен битов. В качестве типового примера, иллюстрирующего полученные ре- зультаты, приведем оценки параметров ));();((log 11102 pCpC ππ −− и );(log 202 pCπ− , рассчитанные для двух линейных кодов ⊥= GC (табл. 1). А.Н. Алексейчук, С.В. Гришаков ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 44 В табл. 1 после символа G указаны значения параметров n , k и d ′ , равных соответственно длине, размерности и минимальному расстоянию кода G ; символ «–» показывает, что соответствующая верхняя граница параметра );( 20 pCπ является тривиальной, то есть превосходит число 1. Т а б л и ц а 1 .Оценки вероятности правильного восстановления сообще- ний в основном и отводном каналах Код )7,45,63(G 1p 10–2 10–4 10–8 Неравенство (16) 1,217 0,012 1,2 . 10–6 Неравенство (17) 0,933 0,009 0,9 . 10–6 2p 0,1 0,2 0,3 0,4 Неравенство (12) 2,253 5,159 9,253 16,253 Неравенство (13) 5,000 11,250 19,286 30,000 Неравенство (14) – – – – Код )106,27,256(G 1p 10–2 10–4 10–8 Неравенство (16) 9,429 0,071 0,7 . 10–5 Неравенство (17) 3,745 0,037 0,4 . 10–5 2p 0,1 0,2 0,3 0,4 Неравенство (12) 26,990 27,000 27,000 27,000 Неравенство (13) 3,000 6,750 11,571 18,000 Неравенство (14) – – 27,000 27,000 Как видно из табл. 1, неравенство (17) в обоих случаях доставляет бо- лее точное приближение параметра );();( 1110 pCpC ππ − по сравнению с формулой (16). Для первого из указанных кодов (имеющего относительно большую скорость передачи 6345=nk ) более точную аппроксимацию параметра );( 20 pCπ обеспечивает оценка (13), а для второго (имеющего относительно малую скорость 25627=nk ) — оценка (12). При этом во втором случае значения );( 20 pCπ быстро приближаются к экстремальному значению k−2 с ростом 2p (например, при 1,02 =p значение параметра );( 20 pCπ заключено в пределах от 272− до 990,262− ). Аналогичное поведе- ние верхних границ (12)–(14) наблюдается для ряда других линейных кодов ,C имеющих достаточно большие длину и дуальное расстояние. В табл. 2 приведены численные значения параметров, характеризую- щих эффективность систем со случайным кодированием кодами ,⊥= ii GC 7,1=i . Как и в табл. 1, тут после символа iG указаны значения парамет- ров n , k и ,d ′ равных соответственно длине, размерности и минимальному расстоянию кода iG , 7,1=i . Неасимптотические оценки эффективности случайного кодирования в системе передачи … Системні дослідження та інформаційні технології, 2011, № 4 45 Т а б л и ц а 2 .Оценки эффективности систем передачи информации по каналу связи с отводом Код )7,45,63(G 1p 10–2 10–4 10–8 t 245 68 67 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 0,0006 3,39 11,35 22,06 0,18 5,18 13,20 23,91 0,18 5,20 13,22 23,93 Код )5,51,63(2G 1p 10–2 10–4 10–8 t 275 77 76 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 0,006 4,67 13,75 25,90 0,35 6,49 15,59 27,73 0,36 6,51 15,61 27,75 Код )84,203,256(3G 1p 10–2 10–4 10–8 t 51440 302 287 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 11,39 46,25 95,39 179,39 18,8053,67102,80186,80 18,8853,74 102,88 186,87 Код )106,229,256(4G 1p 10–2 10–4 10–8 t 57923 340 323 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 18,30 62,30 124,30 213,18 25,71 69,71131,71220,59 25,79 69,78 131,79 220,66 Код )3,247,255(5G 1p 10–2 10–4 10–8 t 61162 366 348 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 11,54 45,85 89,96 148,77 18,9353,23 97,34 156,15 19,0053,31 97,41 156,22 Код )84,53,256(6G 1p 10–2 10–4 10–8 t 14043 83 79 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 13,26 39,22 39,22 39,22 20,67 46,62 46,62 46,62 20,73 46,70 46,70 46,70 Код )106,27,256(7G 1p 10–2 10–4 10–8 t 7560 45 43 2p 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 0,1 0,2 0,3 0,4 ),(ˆ 22 ptλ 14,11 14,12 14,12 14,12 21,50 21,51 21,51 21,51 21,56 21,57 21,57 21,57 А.Н. Алексейчук, С.В. Гришаков ISSN 1681–6048 System Research & Information Technologies, 2011, № 4 46 При этом 1G и 2G являются кодами Боуза-Чоудхури-Хоквингема, а 5G — кодом Хэмминга [12]. Параметры остальных линейных кодов взяты из таблиц, приведенных в [17] (отметим, что 1G и 7G совпадают с кодами, указанными в табл. 1). Символы 1p и 2p в табл. 2 обозначают вероятности ошибок в основном и в отводном каналах связи соответственно, а парамет- ры )( 1ptt = и ),(ˆ 22 ptλ определяются следующим образом. Обозначим );( 11 pCµ наибольшее из двух значений в правых частях неравенств (16) и (17) соответственно при 121 p−=∆ ; );( 22 pCµ — наи- меньшее из трех значений в правых частях неравенств (12), (13), (14) соот- ветственно при 2pp = . Тогда t есть наименьшее натуральное число, удов- летворяющее условию 9,0);( 2 exp21 2 11 ≥ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧−− pCtk µ , (27) а значение ),(ˆ 22 ptλ определяется по формуле )));(1(1(log),(ˆ 22222 tpCpt µλ −−−= , (28) где ⊥= iGC , 7,1=i . Отметим, что на основании неравенств (4) и (27) веро- ятность правильного восстановления сообщения S законным получателем рассматриваемой системы передачи информации по каналу связи с отводом не меньше 9,0 . При этом, согласно формулам (5) и (28), вероятность пра- вильного восстановления этого сообщения противником не превосходит ),(ˆ 222 ptλ− . ВЫВОДЫ В целом, полученные результаты позволяют сделать вывод о том, что при заметном отличии между вероятностями ошибок в основном и отводном каналах можно обеспечить достаточно надежный прием сообщений закон- ным получателем при высокой практической стойкости их защиты в отвод- ном канале, используя сравнительно умеренное число передач t . Так, в сис- теме со случайным кодированием кодом ⊥= 44 GC и вероятностями ошибок 01,01 =p , 3,02 =p для передачи сообщения S длины 229 бит достаточно сформировать случайную последовательность tXX ..., ,1 , состоящую из 57923=t слов, каждое из которых имеет длину 256 битов. Законный полу- чатель, используя алгоритм 1, сможет восстановить S с вероятностью не менее 9,0 , в то время как противник, применяющий более надежный алго- ритм 2, сумеет восстановить S с вероятностью не более чем 3,1242− (при этом вероятность угадывания сообщения S равна 2292− ). Уменьшить значения параметра t удается лишь за счет снижения ско- рости передачи информации. Например, в системе со случайным кодирова- нием кодом ⊥= 66 GC при тех же значениях 1p и 2p для передачи сообще- ния S длины 53 бита достаточно положить 14043=t . При этом законный Неасимптотические оценки эффективности случайного кодирования в системе передачи … Системні дослідження та інформаційні технології, 2011, № 4 47 получатель восстановит переданное сообщение с вероятностью не менее 9,0 , в то время как противник — с вероятностью не более 22,392− (табл. 2). Для повышения скорости передачи информации (при заданных границах надежности ее приема в основном канале связи и стойкости защиты — в отводном) следует, по-видимому, использовать отличные от рассмотрен- ного выше способы случайного кодирования. ЛИТЕРАТУРА 1. Wyner A.D. The wire-tap channel // Bell System Technical Journal. — 1975. — 54. — № 8. — P. 1355–1388. 2. Csiszar I., Korner J. Broadcast channels with confidential messages // IEEE Trans- actions on Information Theory. — 1978. — 24, № 3. — P. 339–348. 3. Коржик В.И., Яковлев В.А. Неасимптотические оценки кодового зашумления одного канала // Проблемы передачи информации. — 1981. — Т. 17. — Вып. 4. — С. 11–18. 4. Коржик В.И., Яковлев В.А. Пропускная способность канала связи с внутренним случайным кодированием // Проблемы передачи информации. — 1992. — Т. 28. — Вып. 4. — С. 24–34. 5. Яковлев В.А. Границы для оценки неопределенности в системе передачи со случайным кодированием // Радиотехника. — 1996. — № 12. — С. 58–63. 6. Иванов В.А. О методе случайного кодирования // Дискретная математика. — 1999. — Т. 11. — Вып. 3. — С. 99–108. 7. Алексейчук А.Н. Оценки эффективности кодовой защиты дискретных сообще- ний с использованием линейных кодов с большим дуальным расстоянием // Реєстрація, зберігання і обробка даних. — 2001. — Т. 3. — № 2. — С. 99–106. 8. Иванов В.А. Асимптотические характеристики критериев проверки гипотез по случайно преобразованной выборке // Тр. по дискретной математике: в 11 т. Т. 5. — М.: Физматлит, 2002. — С. 61–72. 9. Иванов В.А. Статистические методы оценки эффективности кодового зашум- ления // Тр. по дискретной математике: в 11 т. Т. 6. — М.: Физматлит, 2002. — С. 48–63. 10. Алексейчук А.Н., Гришаков С.В. Нелинейное случайное кодирование в систе- мах передачи информации по каналу связи с отводом // Правове, норматив- не та метрологічне забезпечення системи захисту інформації в Україні. — 2004. — Вип. 8. — С. 133–140. 11. Thangaraj A., Dihidar S., Calderbank A.R., McLaughlin S., Merolla J.-M. Capacity achiving codes for the wire-tap channel with applications to quantum key distri- bution. — http://eprint.arXiv:cs.IT/0411003v1. 12. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки: пер. с англ. — М.: Связь, 1979. — 743 с. 13. Ширяев А.Н. Вероятность. — М.: Наука, 1989. — 638 с. 14. Sullivan D. A fundamental inequality between the probabilities of binary subgroups and cosets // IEEE Transactions on Information Theory. — 1967. — 13, № 1. — P. 91–94. 15. Kasami T., Klove T., Lin S. Linear block codes for error detection // IEEE Transactions on Information Theory. — 1983. — 29, № 1. — P. 131–136. 16. Ashikhmin A., Gohen G., Krivelevich M., Litsyn S. Bounds on distance distributions in codes of known size // IEEE Transactions on Information Theory. — 2005. — 51, № 1. — P. 250–258. 17. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. Основные понятия. — М.: МЦНМО, 2003. — 504 с. Поступила 09.10.2009

Неасимптотические оценки еффективности случайного кодирования в системе передачи информации по двоичному симметричному каналу связи с отводом

Institution

Similar Items