Подпишитесь на наши новости
Вернуться к началу с статьи up
 

КАНА́Л СВЯ́ЗИ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 12. Москва, 2008, стр. 701

  • image description

    Скопировать библиографическую ссылку:




Авторы: Ю. В. Прохоров

КАНА́Л СВЯ́ЗИ в тео­рии ин­фор­ма­ции, мате­ма­тич. мо­дель уст­рой­ст­ва, пред­на­зна­чен­но­го для пе­ре­да­чи ин­фор­ма­ции. Ин­фор­ма­ции тео­рия от­вле­ка­ет­ся от кон­крет­ной при­ро­ды та­ких уст­ройств, по­доб­но то­му как гео­мет­рия изу­ча­ет гео­мет­рич. фи­гу­ры и те­ла, от­вле­ка­ясь от ма­те­риа­ла, из ко­то­ро­го они из­го­тов­ле­ны. Разл. кон­крет­ные сис­те­мы свя­зи рас­смат­ри­ва­ют­ся толь­ко с точ­ки зре­ния ко­ли­че­ст­ва ин­фор­ма­ции, ко­то­рое мо­жет быть на­дёж­но пе­ре­да­но с их по­мо­щью. В тео­рии ин­фор­ма­ции К. с. за­да­ёт­ся мно­же­ст­вом $\{x\}$ до­пус­ти­мых со­об­ще­ний (сиг­на­лов) на вхо­де, мно­же­ст­вом $\{y\}$ со­об­ще­ний (сиг­на­лов) на вы­хо­де и на­бо­ром ус­лов­ных ве­ро­ят­но­стей $p(y∣x)$ по­лу­че­ния сиг­на­ла $y$ на вы­хо­де при вход­ном сиг­на­ле $x$. Эти ус­лов­ные ве­ро­ят­но­сти опи­сы­ва­ют ста­ти­стич. свой­ст­ва шу­мов (по­мех), ис­ка­жаю­щих сиг­на­лы в про­цес­се пе­ре­да­чи. В слу­чае ко­гда $p(y∣x)=1$ при $y=x$ для всех $x∈\{x\}$, К. с. на­зы­ва­ет­ся ка­на­лом без шу­мов. В со­от­вет­ст­вии со струк­ту­рой вход­ных и вы­ход­ных сиг­на­лов вы­де­ля­ют дис­крет­ные и не­пре­рыв­ные К. с. В дис­крет­ных К. с. сиг­на­лы на вхо­де и на вы­хо­де пред­став­ля­ют со­бой по­сле­до­ва­тель­но­сти букв из од­но­го и то­го же или разл. ал­фа­ви­тов (см. Код). В не­пре­рыв­ных К. с. вход­ной и вы­ход­ной сиг­на­лы суть функ­ции не­пре­рыв­но­го па­ра­мет­ра, ко­то­рый обыч­но яв­ля­ет­ся вре­ме­нем. Воз­мож­ны так­же сме­шан­ные слу­чаи, но обыч­но пред­по­чи­та­ют рас­смат­ри­вать один из двух ука­зан­ных слу­ча­ев.

Спо­соб­ность К. с. пе­ре­да­вать ин­фор­ма­цию ха­рак­те­ри­зу­ет­ся не­ко­то­рым чис­лом – про­пу­ск­ной спо­соб­но­стью (ём­ко­стью) ка­на­ла, ко­то­рая оп­ре­де­ля­ет­ся как макс. ко­ли­че­ст­во ин­фор­ма­ции от­но­си­тель­но сиг­на­ла на вхо­де, со­дер­жа­щее­ся в сиг­на­ле на вы­хо­де (в рас­чё­те на еди­ни­цу вре­ме­ни). Точ­нее, пусть вход­ной сиг­нал $X$ при­ни­ма­ет зна­че­ния $x∈\{x\}$ с ве­ро­ят­но­стя­ми $p(x)$. То­гда по фор­му­лам тео­рии ве­ро­ят­но­стей мож­но рас­счи­тать как ве­ро­ят­но­сти $q(y)$ то­го, что сиг­нал $Y$ на вы­хо­де при­мет зна­че­ние $y$, $q(y)=\sum_xp(x)p(y|x)$, так и ве­ро­ят­но­сти $p(x, y)$ со­вме­ще­ния со­бы­тий $X=x, Y=y, p(x, y)=p(x)p(y|x)$. По этим ве­ли­чи­нам вы­чис­ля­ет­ся ко­ли­че­ст­во ин­фор­ма­ции $$I(Y, X)=I(X, Y)=\sum_{x, y}p(x, y)\log_2(p(x, y)/p(x)q(y))$$ и его ср. зна­че­ние на еди­ни­цу вре­ме­ни $$R=\lim_{T→∞}\frac{1}{T}I(Y, X),$$где $T$ – дли­тель­ность пе­ре­да­чи сиг­на­ла $X$. Верх­няя гра­ни­ца $C$ ве­ли­чин $R$, взя­тая по всем ис­точ­ни­кам со­об­ще­ний на вхо­де, на­зы­ва­ет­ся про­пу­ск­ной спо­соб­но­стью К. с. Вы­чис­ле­ние про­пу­ск­ной спо­соб­но­сти, по­доб­но вы­чис­ле­нию эн­тро­пии, лег­че в дис­крет­ном слу­чае и слож­нее в не­пре­рыв­ном, где оно ос­но­вы­ва­ет­ся на тео­рии ста­цио­нар­ных слу­чай­ных про­цес­сов.

В тео­рии ин­фор­ма­ции ус­та­нав­ли­ва­ет­ся, что в слу­чае дис­крет­но­го К. с. без шу­мов об­щее оп­ре­де­ле­ние про­пу­ск­ной спо­соб­но­сти $C$ рав­но­силь­но сле­дую­ще­му: $$C=\lim_{T→∞}\frac{\log_2N(T)}{T},$$ где $N(T)$ – чис­ло до­пус­ти­мых сиг­на­лов дли­тель­но­сти $T$.

При­мер 1. Пусть вход­ной ал­фа­вит К. с. без шу­мов со­сто­ит из сим­во­лов (букв) 0 и 1, пе­ре­да­ча ка­ж­до­го из ко­то­рых за­ни­ма­ет $\textτ$ се­кунд. До­пус­ти­мые сиг­на­лы дли­тель­но­стью $T=n\textτ$ пред­став­ля­ют­ся по­сле­до­ва­тель­но­стя­ми дли­ны $n$ сим­во­лов 0 и 1. Их чис­ло $N(T)=2^n$. В этом слу­чае $$C=\lim_{T→∞}\frac{\log_2N(T)}{T}=\lim_{n→∞}\frac{n}{n\textτ}=\frac{1}{\textτ}\text{(дво­ич­ные ед./с).}$$ 

При­мер 2. Пусть сим­во­лы 0 и 1 пе­ре­да­ют­ся за $\textτ$ и $2\textτ$ с со­от­вет­ст­вен­но. Здесь до­пус­ти­мых сиг­на­лов дли­тель­но­стью $T=n\textτ$ бу­дет мень­ше, чем в при­ме­ре 1. Так, при $n=3$ их бу­дет все­го 3 (вме­сто 8). Мож­но под­счи­тать, что $$C=\frac{1}{\textτ}\log_2 \left(\frac{\sqrt{5}+1}{2}\right)\approx\frac{0{,}7}{\textτ}\text{(дво­ич­ные ед./с).}$$

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

При­мер 3. Пусть ис­точ­ник со­об­ще­ний по­сы­ла­ет не­за­ви­си­мо друг от дру­га че­рез про­ме­жут­ки вре­ме­ни дли­ны $1/v$ (т. е. со ско­ро­стью $v$) сим­во­лы $x$ (бу­к­вы со­об­ще­ния), при­ни­маю­щие зна­че­ния $x_1, x_2, x_3, x_4$ с ве­ро­ят­но­стя­ми, рав­ными со­от­вет­ст­вен­но 1/2, 1/4, 1/8, 1/8. Пусть К. с. без шу­мов та­кой же, как в при­мере 1, и ко­ди­ро­ва­ние осу­ще­ст­в­ля­ет­ся мгно­вен­но. По­лу­чен­ный сиг­нал или пе­ре­да­ёт­ся по К. с., ес­ли по­след­ний сво­бо­ден, или ожи­да­ет (по­ме­ща­ет­ся в па­мять) до тех пор, по­ка К. с. не ос­во­бо­дит­ся. Ес­ли вы­бран, напр., код $x_1=00, x_2=01, x_3=10, x_4=11$ и $v⩽\textτ/2$ (т. е. $1/v⩾2\textτ$), то за вре­мя ме­ж­ду по­яв­ле­нием двух по­сле­до­ват. зна­че­ний $x$ ко­довое обо­зна­че­ние пер­во­го из них ус­пе­ва­ет пе­ре­дать­ся и К. с. ос­во­бо­ж­да­ет­ся. Т. о., здесь ме­ж­ду по­яв­ле­ни­ем к.-л. бу­к­вы со­об­ще­ния и пе­ре­да­чей её ко­до­во­го обо­зна­че­ния по К. с. про­хо­дит про­ме­жу­ток вре­ме­ни $2\textτ$. Ес­ли $v>\textτ/2$, то $n$-я бу­к­ва со­об­ще­ния по­яв­ля­ет­ся в мо­мент $(n-1)/v$ и её ко­до­вое обо­зна­че­ние бу­дет пе­ре­да­но по К. с. в мо­мент $2n\textτ$. Про­ме­жу­ток вре­ме­ни ме­ж­ду по­яв­ле­ни­ем $n$-й бу­к­вы со­об­ще­ния и мо­мен­том её по­лу­че­ния по­сле де­ко­ди­ро­ва­ния пе­ре­дан­но­го сиг­на­ла бу­дет боль­ше, чем $n(2\textτ-1/v)$, эта ве­ли­чи­на стре­мит­ся к бес­ко­неч­но­сти при $n→∞$, т. е. в этом слу­чае пе­ре­да­ча бу­дет вес­тись с не­ог­ра­ни­чен­ным за­паз­ды­ва­ни­ем. По­это­му для воз­мож­но­сти пе­ре­да­чи без не­ог­ра­ни­чен­но­го за­паз­ды­ва­ния при дан­ном ко­де не­об­хо­ди­мо и дос­та­точ­но вы­пол­не­ние ус­ло­вия $v⩽\textτ/2$. Вы­бо­ром бо­лее удач­но­го ко­да мож­но уве­ли­чить ско­рость пе­ре­да­чи, сде­лав её сколь угод­но близ­кой к про­пу­ск­ной спо­соб­ности К. с., но эту по­след­нюю гра­ни­цу не­воз­мож­но пре­взой­ти (со­хра­няя тре­бо­ва­ние ог­ра­ни­чен­но­сти за­паз­ды­ва­ния). Сфор­му­ли­ро­ван­ное ут­вер­жде­ние име­ет об­щий ха­рак­тер и на­зы­ва­ет­ся осн. тео­ре­мой о К. с. без шу­мов.

В от­но­ше­нии при­ме­ра 3 мож­но до­ба­вить сле­дую­щее. Для рас­смат­ри­вае­мых со­об­ще­ний, ко­то­рые по­яв­ля­ют­ся с ука­зан­ны­ми ве­ро­ят­но­стя­ми, оп­ти­ма­лен дво­ич­ный код $x_1=0, x_2=10, x_3=110, x_4=111$. Из-за разл. дли­ны ко­ди­ро­ван­ных со­об­ще­ний вре­мя за­паз­ды­ва­ния для $n$-й бу­к­вы пер­во­на­чаль­но­го со­об­ще­ния бу­дет слу­чай­ной ве­ли­чи­ной. При $v<1/\textτ$ ($1/τ$ – про­пу­ск­ная спо­соб­ность К. с.) и $n→∞$ его ср. зна­че­ние при­бли­жа­ет­ся к не­ко­то­ро­му пре­де­лу $m(v)$, за­ви­ся­ще­му от $v$. С при­бли­же­ни­ем $v$ к кри­тич. зна­че­нию $1/\textτ$ зна­че­ние $m(v)$ рас­тёт про­пор­цио­наль­но $(\textτ–1-v)–1$. Это от­ра­жа­ет об­щее по­ло­же­ние: при при­бли­же­нии ско­ро­сти пе­ре­да­чи к мак­си­маль­ной воз­рас­та­ют вре­мя за­паз­ды­ва­ния и не­об­хо­ди­мый объ­ём па­мя­ти ко­ди­рую­ще­го уст­рой­ст­ва.

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

При­мер 4. Пусть вход­ной ал­фа­вит К. с. со­сто­ит из двух сим­во­лов 0 и 1 и дей­ст­вие шу­мов сво­дит­ся к то­му, что ка­ж­дый из этих сим­во­лов при пе­ре­да­че мо­жет с не­боль­шой ве­ро­ят­но­стью $p$ пе­рей­ти в дру­гой или с ве­ро­ят­но­стью $q=1-p$ ос­тать­ся не­ис­ка­жён­ным. При­ме­не­ние по­ме­хо­устой­чи­во­го ко­да сво­дит­ся, по су­ти де­ла, к вы­бо­ру но­во­го ал­фа­ви­та на вхо­де К. с. Его бу­к­ва­ми яв­ля­ют­ся $n$-член­ные це­поч­ки сим­во­лов 0 и 1, от­ли­чаю­щие­ся од­на от дру­гой дос­та­точ­ным чис­лом $d$ зна­ков. Так, при $n=$ 5 и $d=$ 3 но­вы­ми бу­к­ва­ми мо­гут быть 00000, 01110, 10101, 11011. По­сколь­ку при ма­лых $p$ ве­ро­ят­ность бо­лее чем од­ной ошиб­ки на груп­пу из пя­ти зна­ков ма­ла, то, да­же ис­ка­жён­ные, эти бу­к­вы поч­ти не пе­ре­пу­ты­ва­ют­ся. Напр., ес­ли по­лу­чен сиг­нал 10001, то он, ско­рее все­го, воз­ник из 10101. Ока­зы­ва­ет­ся, что при над­ле­жа­щем вы­бо­ре дос­та­точ­но боль­ших $n$ и $d$ та­кой спо­соб зна­чи­тель­но эф­фек­тив­нее про­сто­го по­вто­ре­ния (т. е. ис­поль­зо­ва­ния ал­фа­ви­тов ти­па 000, 111). Од­на­ко воз­мож­ное на этом пу­ти улуч­ше­ние ка­че­ст­ва пе­ре­да­чи со­пря­же­но с воз­рас­таю­щей слож­но­стью ко­ди­рую­щих и де­ко­ди­рую­щих уст­ройств. Напр., ес­ли пер­во­на­чаль­но $p=10^{–2}$ и тре­бу­ет­ся умень­шить это зна­че­ние до $p_1=10^{–4}$, то сле­ду­ет вы­би­рать дли­ну $n$ ко­до­вой це­поч­ки не ме­нее 25 (или 380) в за­ви­си­мо­сти от то­го, же­ла­ют ли ис­поль­зо­вать про­пу­ск­ную спо­соб­ность К. с. на 53% (или на 80%).

В кон. 20 в. в свя­зи с раз­ви­ти­ем кван­то­вой тео­рии ин­фор­ма­ции и кван­то­вых ком­пь­ю­те­ров поя­ви­лись и ис­сле­ду­ют­ся кван­то­вые ка­на­лы свя­зи.

Лит. см. при ст. Ин­фор­ма­ция.

Вернуться к началу