¥Ö¥í¥Ã¥¯Éä¹æ¤Î¿ô³ØŪ¥â¥Ç¥ë

¾ðÊó¤òk¥Ó¥Ã¥ÈËè¤Î¥Ö¥í¥Ã¥¯¤Ë¶èÀÚ¤ê, ¥Ö¥í¥Ã¥¯Ëè¤ËÉä¹æ²½¤·¤ÆÁ÷¿®¤¹¤ë¥Ö¥í¥Ã¥¯Éä¹æ¤¬¿ô³ØŪ¤Ë¤É¤¦µ­½Ò¤µ¤ì¤ë¤«, ¤½¤·¤Æ¤É¤Î¤è¤¦¤ÊÀ­¼Á¤ò»ý¤Ä¤«¤ò¹Í¤¨¤Æ¤ß¤è¤¦.

B¤ò0¤È1¤ÎÆó¤Ä¤Î¸µ¤«¤é¤Ê¤ë½¸¹ç$\{0,1\}$¤È¤¹¤ë¤È, 0¤È1¤«¤é¤Ê¤ëk¥Ó¥Ã¥È¤Î¿®¹æÁ´ÂΤÏB¤Îk¸Ä¤ÎľÀÑB^k¤ÈƱ°ì»ë¤Ç¤­¤ë.

$$B^k=\{(x_1,x_2,\dots,x_k)\vert x_i\in B=\{0,1\}, i=1,2,\dots,... ...longleftrightarrow x_1x_2\cdots x_k \text{ : $k$¥Ó¥Ã¥È¤Î¿®¹æ}$$

Îã 4.1  

$$\begin{array}{ccc} \text{$B^3$¤Î¸µ}&&\text{3¥Ó¥Ã¥È¤Î¿®¹æ} \\ ... ...& & 101 \\ (1,1,0) & & 110 \\ (1,1,1) & & 111 \\ \end{array}$$

¿ô»ú¤ò°ì¸Ä¤º¤Ä¤Ð¤é¤·¤Æ³ç¸Ì¤ËÆþ¤ì¤¿¤À¤±¤È»×¤¦¤«¤âÃΤì¤Ê¤¤¤¬, ¤½¤ÎÄ̤ê¤Ç¤¢¤ë. ¤¿¤À, ¤³¤¦¤¹¤ë¤³¤È¤Ç, ¼¡¤Î¤è¤¦¤Ê¡Ö¿ô³Ø¡×Ūɽµ­¤¬²Äǽ¤Ë¤Ê¤ë¤Î¤Ç¤¢¤ë.

³Æk¥Ó¥Ã¥È¤Î¿®¹æ¤Ël¥Ó¥Ã¥È¤Î;ʬ¤Ê¾ðÊó¤òÉղä·¤ÆÁ÷¤ë¥Ö¥í¥Ã¥¯Éä¹æ¤ò¹Í¤¨¤ë¤³¤È¤Ë¤¹¤ë¤È, ¤³¤ÎÉä¹æ²½¤Ï¼¡¤Î¤è¤¦¤Ë¥â¥Ç¥ë²½¤µ¤ì¤ë.

$$B^k \overset{\varphi}{\to} B^n \text{ : ñ¼Í (¤¿¤À¤·, $n=k+l>k$)}$$

${\mathbf x}\in B^k$¤ËÂФ·, $\varphi({\mathbf x})\in B^n$¤¬ x¤ÎÉä¹æ²½¤µ¤ì¤¿¤â¤Î¤È¤¤¤¦¤ï¤±¤Ç¤¢¤ë(ñ¼Í¤È¤¤¤¦¾ò·ï¤¬É¬ÍפʤΤÏ, °ã¤¦¥Ç¡¼¥¿¤¬Éä¹æ²½¤·¤ÆƱ¤¸¤â¤Î¤Ë¤Ê¤Ã¤Æ¤Ï, Éü¹æ¤¬¤Ç¤­¤Ê¤¯¤Ê¤ë¤«¤é¤Ç¤¢¤ë). ¤³¤Î¤è¤¦¤Ë¥â¥Ç¥ë²½¤µ¤ì¤ë¥Ö¥í¥Ã¥¯Éä¹æ¤Ë¤Ä¤¤¤Æ, k¤ò¾ðÊóĹ(information length), n¤òÉä¹æĹ(code length), n-k¤ò¾éĹÀ­(redundancy), k/n¤òÉä¹æ²½Î¨(infomation rate, ¤Þ¤¿¤Ï code rate)¤È¤¤¤¤, Éä¹æĹn, ¾ðÊóĹk¤ÎÉä¹æ¤ò(n,k)-Éä¹æ¤È¤¤¤¦. ¤Þ¤¿, ñ¼Í$\varphi$¤Ë¤è¤ëB^k¤ÎÁü $\operatorname{Im}\varphi$¤òÉä¹æ(code)¤È¤¤¤¤, $\operatorname{Im}\varphi$¤Î¸µ¤òÉä¹æ¸ì¤È¤¤¤¦. °Ê²¼, $\operatorname{Im}\varphi$¤òC¤È½ñ¤¯¤³¤È¤Ë¤¹¤ë.

ÍѸì¤Î¤Þ¤È¤á
Éä¹æĹ	=	Éä¹æ¤Î¥Ó¥Ã¥È¿ô
¾ðÊóĹ	=	¾ðÊó¥Ó¥Ã¥È¤ÎŤµ
¾éĹÀ­	=	Éä¹æĹ-¾ðÊóĹ
Éä¹æ²½Î¨	=	¾ðÊóĹ¡¿Éä¹æĹ

ÌäÂê 4.2   Îã, Îã¤ÎÉä¹æ¤Ë¤Ä¤¤¤Æ, Éä¹æĹ, ¾ðÊóĹ, ¾éĹÀ­, Éä¹æ²½Î¨¤òµá¤á¤Æ¤ß¤è¤¦.

°Ê¾å¤Îµ­¹æ¤Î²¼¤Ç, ¥Ö¥í¥Ã¥¯Éä¹æ¤Î¸í¤êÄûÀµ¤Ë¤Ä¤¤¤Æ¹Í¤¨¤Æ¤ß¤è¤¦.¤½¤Î¤¿¤á¤Ë, ¤Þ¤º¥Ï¥ß¥ó¥°µ÷Î¥¤È¤¤¤¦³µÇ°¤òƳÆþ¤¹¤ë.

ÄêµÁ 4.3   ${\mathbf x},{\mathbf y}\in B^n$¤ËÂФ·, $\sharp\{i \vert x_i\not= y_i\}$(¤¹¤Ê¤ï¤Á°Û¤Ê¤ëÀ®Ê¬¤Î¸Ä¿ô) ¤ò x¤È y¤Î¥Ï¥ß¥ó¥°µ÷Î¥¤È¤¤¤¤, d(x,y)¤Çɽ¤¹. ¤³¤ì¤Ïµ÷Î¥¤Î¸øÍý¤òËþ¤¿¤¹ .

Îã 4.4   Î㤨¤Ð, n=4¤Î¾ì¹ç, d((0,0,0,0), (0,0,0,1))=1, d((0,1,0,1), (1,1,0,0))=2¤Ê¤É¤È¤È¤Ê¤ë.

¤µ¤Æ, Éä¹æ¸ì ${\mathbf x}\in C$¤òÁ÷¿®¤·¤Æ, ¼õ¤±¼ê¤¬¼õ¿®¤·¤¿¼õ¿®¸ì¤¬ x'¤À¤Ã¤¿¤È¤¹¤ë¤È¤­,

$$\underline{ \text{Éä¹æ¸ì${\mathbf x}\in C$¤Ë¤Ä¤¤¤ÆÁ÷¿®Ãæ¤Ë¥¨¥é¡¼¤¬µ¯¤­¤ë} \Longleftrightarrow {\mathbf x}\not= {\mathbf x}'}$$

¤Ç¤¢¤ë¤«¤é, ¤³¤Î¥Ï¥ß¥ó¥°µ÷Î¥¤ò»È¤¦¤È,

$$\underline{ \text{Éä¹æ¸ì${\mathbf x}\in C$¤Ë¤Ä¤¤¤ÆÁ÷¿®Ãæ¤Ë¥¨¥... ...µ¯¤­¤ë} \Longleftrightarrow d({\mathbf x},{\mathbf x}')\not=0}$$

¤Èɽ¸½¤µ¤ì¤ë¤³¤È¤¬Ê¬¤«¤ë.

¤¢¤ëÄÌ¿®¤ò¹Ô¤Ã¤Æ, ¼õ¿®Â¦¤¬ ${\mathbf x}'\in B^n$¤È¤¤¤¦¼õ¿®¸ì¤ò¼õ¤±¼è¤Ã¤¿¤È¤¹¤ë. ¼õ¿®Â¦¤ÏÅöÁ³Á÷¿®¸ì¤¬²¿¤Ç¤¢¤Ã¤¿¤«ÃΤë¤è¤·¤â¤Ê¤¤¤«¤é, ¼õ¿®¸ì¤«¤éÁ÷¿®¸ì¤òÅö¤Æ¤ë(Éü¸µ¤¹¤ë)¤³¤È¤¬É¬ÍפȤʤë. ¤³¤ì¤Ë¤Ï¤É¤¦¤¹¤ì¤Ð¤è¤¤¤À¤í¤¦¤«¡©

¤¤¤Þ, ³Æ¥Ó¥Ã¥È¤ËÂФ·¤Æ, ¸í¤ê¤¬À¸¤¸¤ë³ÎΨ¤¬¤É¤ì¤âÅù¤·¤¯ÆÈΩ¤Ëp¤Ç¤¢¤ë¤È¤·¤è¤¦(2¸µÂоÎÄÌ¿®Ï©). p¤ÏÄÌ¿®Ï©¤Î¥Ï¡¼¥ÉŪ¤ÊÆÃÀ­¤«¤éÄê¤Þ¤ëÈó¾ï¤Ë¾®¤µ¤¤¿ô¤Ç¤¢¤ë¤¬(¤È¤¤¤¦¤«½½Ê¬¾®¤µ¤¯¤Ê¤±¤ì¤Ð¿®ÍѤΤª¤±¤ëÄÌ¿®Ï©¤È¤Ê¤é¤Ê¤¤), ¤³¤³¤Ç¤ÏÊص¹¾åp=10^-a, (a>1)¤È¤Ç¤â¤·¤Æ¤ª¤³¤¦. ¤¹¤ë¤È, x¤¬ÄÌ¿®Ãæ¤Î¥¨¥é¡¼¤Ç y¤Ë¤Ê¤ë³ÎΨ $P({\mathbf x}\to{\mathbf y})$¤Ï,

$$P({\mathbf x}\to{\mathbf y})\sim 10^{-ad({\mathbf x},{\mathbf y})}$$

¤È¤Ê¤ë¤«¤é, ${\mathbf x}_1,{\mathbf x}_2\in C$¤ËÂФ·¤Æ,

$$d({\mathbf x}',{\mathbf x}_1)<d({\mathbf x}',{\mathbf x}_2) ... ...to{\mathbf x}')>\hspace{-2pt}>P({\mathbf x}_2\to{\mathbf x}')$$

¤Ç¤¢¤ê, x'¤Ë¥Ï¥ß¥ó¥°µ÷Î¥¤Ç¶á¤¤°ÌÃ֤ˤ¢¤ë¤â¤Î¤Û¤É x'¤ÎÁ÷¿®¸ì¤Ç¤¢¤ë³ÎΨ¤¬¹â¤¤(¶Ïº¹¤Ç¤Ï¤Ê¤¯°µÅÝŪ¤Ë¹â¤¤)¤³¤È¤¬Ê¬¤«¤ë. ¤·¤¿¤¬¤Ã¤Æ, ºÇ¤â¸¶»ÏŪ¤Ê¸í¤êÄûÀµ¤ÎÊýË¡¤È¤·¤Æ, x'¤È¤Î¥Ï¥ß¥ó¥°µ÷Î¥¤¬°ìÈÖ¾®¤µ¤¤C¤Î¸µ¤òÁ÷¿®¸ì¤À¤È¡Ö»×¤¦¡×(ÅöÁ³¥Ï¥º¥ì¤Æ¤¤¤ë¤³¤È¤â¤¢¤ë)¤È¤¤¤¦Éü¹æË¡¤¬¹Í¤¨¤é¤ì¤ë¤Ç¤¢¤í¤¦. ¤³¤ì¤òºÇÌàÉü¹æ(ºÇ¤âÌà¤â¤é¤·¤¤¤â¤Î¤òÂò¤ë¤È¤¤¤¦°ÕÌ£)¤È¤¤¤¦.

¤³¤ì¤Ç¤¹¤Ù¤Æ¤¬¾å¼ê¤¯¤¤¤±¤Ð¤è¤¤¤Î¤À¤¬, »ÄÇ°¤Ê¤¬¤éºÇÌàÉü¹æ¤Ë¤Ï¼¡¤Î¤è¤¦¤Ê¼åÅÀ¤¬¤¢¤ë.

1.

C¤Î¸µ¤òÁíÅö¤¿¤ê¤ÇÄ´¤Ù¤ë¤Î¤Ç, ²¿¤È¤¤¤Ã¤Æ¤â»þ´Ö¤¬¤«¤«¤ë.

2.

°ìÈֶᤤ¤È¤³¤í¤Ë¤¢¤ë¤â¤Î¤¬°ì¤Ä¤À¤±¤È¤Ï¸Â¤é¤Ê¤¤.

¤³¤¦¤¤¤Ã¤¿¼åÅÀ¤ò²þÁ±¤·¤¿Éü¹æ¤¬, º£¤«¤é½Ò¤Ù¤ëºÇ¾®µ÷Î¥Éü¹æ¤Ç¤¢¤ë. ¤³¤ì¤òÀâÌÀ¤¹¤ë¤¿¤á¤Ë, ¼¡¤ÎÎ̤¬Âç»ö¤Ë¤Ê¤ë.

ÄêµÁ 4.5   Éä¹æ $C\subset B^n$¤ËÂФ·, $\min \{ d({\mathbf x},{\mathbf y}) \vert {\mathbf x},{\mathbf y}\in C, {\mathbf x}\not={\mathbf y}\}$¤òC¤ÎºÇ¾®µ÷Î¥¤È¤¤¤¤, d(C)¤Þ¤¿¤Ï, ñ¤Ëd¤È½ñ¤¯. ¤Þ¤¿, ºÇ¾®µ÷Î¥¤¬d¤Î(n,k)-Éä¹æ¤ò(n,k,d)-Éä¹æ¤È¤¤¤¦.

¼õ¿®¸ì ${\mathbf x}'\in B^n$¤ËÂФ·¤Æ,

$$C_{{\mathbf x}'}:=\left\{{\mathbf y}\in C \left\vert d({\mathbf x}',{\mathbf y})< \frac{d}{2}\right.\right\}$$

¤È¤¤¤¦½¸¹ç¤ò¹Í¤¨¤ë. ¤¹¤ë¤È, d¤¬C¤ÎºÇ¾®µ÷Î¥¤Ç¤¢¤ë¤³¤È¤«¤é, Ǥ°Õ¤Î ${\mathbf x}'\in B^n$¤ËÂФ·¤Æ, $C_{{\mathbf x}'}=\phi$¤«¤Þ¤¿¤Ï C_x'¤ÏÍ£°ì¤Ä¤Î¸µ¤«¤é¤Ê¤ë. ¤³¤Î¤È¤­, ¼õ¿®¸ì ${\mathbf x}'\in B^n$¤ËÂФ·¤Æ,

$$\begin{cases} \text{$C_{{\mathbf x}'}=\{{\mathbf y}\}\not=\p... ...{$C_{{\mathbf x}'}=\phi$¤Ê¤é¤Ð, } & \text{Äü¤á¤ë} \end{cases}$$

¤Ë¤è¤Ã¤Æ¼õ¿®¸ì¤«¤é¤Î¸í¤êÄûÀµ¤ò¹Ô¤¦Éü¹æË¡¤òºÇ¾®µ÷Î¥Éü¹æ¤È¤¤¤¦(²¼¿Þ»²¾È).

ºÇ¾®µ÷Î¥Éü¹æ¤òÍѤ¤¤¿¸í¤êÄûÀµ¤Ë¤ª¤¤¤Æ¤Ï, Éü¹æ¤òÄü¤á¤ë¾ì¹ç¤ò½ü¤¤¤Æ, Í£°ì¤Ä¤ÎC¤Î¸µ¤Ø¤ÈÉü¹æ¤µ¤ì¤ë. Éü¹æ¤Î¸õÊä¤ò¥Ï¥ß¥ó¥°µ÷Î¥¤¬d/2̤Ëþ¤Î °ÌÃ֤ˤ¢¤ë¤â¤Î¤Ë¹Ê¤ë¤³¤È¤Ç, Éü¹æ»þ´Ö¤¬ÀáÌ󤵤ì, ¤Þ¤¿Æ±»þ¤Ë, Éü¹æ¤Ç¤­¤ë ¾ì¹ç¤Ë¤ÏÍ£°ì¤Ä¤ËÄê¤Þ¤ë¤³¤È¤¬Êݾڤµ¤ì¤ë¤³¤È¤Ë¤Ê¤ë. Éü¹æ¤Ç¤­¤Ê¤¤¾ì¹ç¤Ï Äü¤á¤ë¤Ê¤ó¤Æ¤¤¤¤²Ã¸º¤Ê¤³¤È¤Ç¤É¤Ê¤¤¤¹¤ó¤Í¤ó, ¤ÈÊ°¤ê¤ò´¶¤¸¤é¤ì¤ëÊý¤â ¤¤¤ë¤À¤í¤¦¤¬, Éü¹æ¤Ç¤­¤Ê¤¤¾ì¹ç¤Ï, ºÆÁ÷¤òÍ׵᤹¤ë¤Ê¤ê²¿¤Ê¤êÊ̤ÎÊýË¡¤ò ºÎ¤ì¤Ð¤è¤¤¤À¤±¤Î¤³¤È¤Ç¤¢¤ë. °Ê¸å, ËܹƤǤÏ, ºÇ¾®µ÷Î¥Éü¹æ¤Î¤ß¤ò¹Í¤¨¤ë¤³¤È¤Ë¤¹¤ë .

Ãí°Õ 4.6   ºÇÌàÉü¹æ, ºÇ¾®µ÷Î¥Éü¹æ¤È¤â¤Ë, ¸í¤êÄûÀµÇ½ÎϤ˴ؤ·¤Æ¤Ï, BⁿÆâ¤ÎC¤ÎÅÀ¤Î»¶¤é¤Ð¤êÊý(¸ß¤¤¤ËÎ¥¤ì¤Æ¤¤¤ì¤Ð¤¤¤ë¤Û¤É¤è¤¤)¤Î¤ß¤Ë°Í¸¤·, Á´Ã±¼Í $\varphi : B^k \to C$¤ÎÄê¤áÊý¤Ë¤Ï̵´Ø·¸¤Ç¤¢¤ë¤³¤È¤ËÃí°Õ¤·¤Æ¤ª¤³¤¦. ¤â¤Á¤í¤ó, $\varphi$¤âÉä¹æ²½¤ÈÉü¹æ¤Î¥×¥í¥»¥¹¤òô¤¦Âç»ö¤Ê¼ÌÁü¤Ç¤Ï¤¢¤ë¤¬, º£¸å, Éä¹æ¤òµÄÏÀ¤¹¤ë¤È¤­, ¤·¤Ð¤·¤Ð$\varphi$¤Î¤³¤È¤Ï˺¤ì¤ÆC¤Î¤ß¤ò¹Í¤¨¤ë¤³¤È¤Ë¤Ê¤ë.