Крафтын тэнцэтгэл биш

Кодчлолын онолоор (coding theory) Крафтын тэнцэтгэл биш (Леон Крафтын нэрээр нэрлэгдсэн) нь префикс код (prefix code) бүрдүүлэх хангалттай нөхцлийг бүрдүүлэхээс (uniquely decodable code) гадна өгөгдсөн урттай нууц үгийн тайлагдагдахгүй байх кодыг бүрдүүлэхэд чухал үүрэг гүйцэтгэдэг. Энэхүү тэнцэтгэл биш нь компьютерийн шинжлэх ухаан болон мэдээлэл технелогийн префикс код болон модны хүрээнд хэрэглэгддэг.

Цаашилбал, Крафтын тэнцэтгэл биш нь префикс кодын(prefix code) нууц үгийн уртыг хязгаарладаг болно. Жишээ нь: хэрэв ашиглагдаж буй нууц үгийн (codeword) уртын илтгэгч функцыг авахад үлдсэн утга нь магадлалын олонлогын функцтэй төстэй утга үлдэх бөгөөд нийт хэмжээ нь 1-ээс бага буюу тэнцүү байна. Крафтын тэнцэтгэл биш нь нууц үгийн хүрээнд зарцуулах нэгдсэн нөөцөнд хүндрэлтэй тусах бөгөөд нууц үг богино байх тусам илүү хүндрэлтэй байна.

• Хэрэв Крафтын тэнцэтгэл биш нь тодорхой тэнцэл биш агуулж байвал кодын хувьд илүүдэлтэй байна.
• Хэрэв Крафтын тэнцэтгэл биш нь тэнцэл биш агуулж байвал асуулгыг бүрэн код гэнэ.
• Хэрэв Крафтын тэнцэтгэл биш нь тэнцэл биш хэлбэртэй бол код нь цор ганц задлагч (uniquely decodable) байна .

Крафтын тэнцэтгэл бишийг 1949 онд Крафт гаргаж ирсэн. Гэхдээ Крафтын судалгаанд зөвхөн префикс кодын талаар л бичсэн ба Раймонд Рэдхэффэрийн тэнцэл биштэй адилтгаж анализ хийсэн байдаг. 1956 онд МкМиллан (1956)-ийн энэхүү тэнцэл бишийг ашиглан гаргасан нээлтийн дараа энэхүү тэнцэл бишийг Крафт-МкМилланын теором гэж мөн хэлэх болсон. 1955 онд Joseph Leo Doob-ны гаргаж байсан цор ганц задлагч uniquely decodable кодын ерөнхий байдал болон зарин хэлбэрийн префикс кодын шинж чанарыг МкМиллан (1956)нь энэхүү тэнцэл бишийг ашиглан нотолсон юм.

Жишээ

Хоёртын мод

9, 14, 19, 67, 76 нь модны навчнуудын оройнууд бөгөөд харгалзах өргөн нь 3, 3, 3, 3 болон 2 болно

Хоёртын модны (binary tree)навчнуудаар префикс кодын тодорхойлж болохыг Крафтын тэнцэтгэл биш нь баталдаг.

$\sum _{\ell \in \mathrm {leaves} }2^{-\mathrm {depth} (\ell )}\leq 1.$

Энд нийлбэр нь нийт навчны нийлбэрүүд бөгөөд. Ямар нэгэн хүүхэдгүй(No child) орой. Өргөн нь үзүүрийн язгуурын зай болно.

${\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leq 1.$

Чайтингийн тогтмол

Мэдээллийн технологийн шинжлэх ухааны алгоритмийн онолын хувьд Чайтины (Chaitin) тогтмол нь

$\Omega =\sum _{p\in P}2^{-|p|}.$

Энэ нь хязгааргүй нийлбэр бөгөөд бичлэгийн хувьд зөв ч гацаж буй програмын хувьд нэг нэмэгдэхүүн байна.|p| нь p-гийн бит-ийн эгнээний уртыг тодорхойлно. Зөв бичигдсэн ч гацаж буй програмын хувьд префикс агуулсан нэмэгдэхүүн байхгүй бөгөөд иймд програм нь префикс код байхгүй байх шаардлагатай. Гэвч битийн эгнээ нь префикс код тул Крафтын тэнцэтгэл бишээр $\Omega \leq 1$.

Тодорхойлолт

Эх үүсвэр бүрийг үсгээр тэмдэглэн

$S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}\,$

цор ганц задлах нь $r$ нь үсэг хүртэл кодлох ба нууц үгийн урт нь дараахи байдлаар илэрхийлэгдэнэ.

$\ell _{1},\ell _{2},\ldots ,\ell _{n}.\,$

тэгэхээр

$\sum _{i=1}^{n}\left({\frac {1}{r}}\right)^{\ell _{i}}\leq 1.$

Тухайн $\ell _{1},\ell _{2},\ldots ,\ell _{n}\,$ -ийн хүрээнд дээрх тэнцэл бишийг хангаж буй дурын натурал тоонуудын хувьд эдгээр нууц үгийн урттай цор ганц задлах код нь $r$ үсгийн хэмжээнд оршиж байдаг.

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

Префикс кодын баталгаа

2-тын модны жишээ. Улаан өнгөөр тэмдэглэсэн зангилаа нь префикс кодыг тодоор илэрхийлнэ. Тухайн зангилаанаас салаалж буй салаануудын тоог тооцоолох аргачлалыг доор үзүүлж байна.

Дээрхээс $\ell _{1}\leq \ell _{2}\leq ...\leq \ell _{n}$ гэж үзвэл $A$ нь $r$-тын модны $\ell _{n}$-ын нийт өргөн болно. $\ell _{n}$-тын модны $r$ өргөний салаа бүрийн үсгийн хувьд урт нь $\ell \leq \ell _{n}$ байна. Префикс кодын $r$-дэх үгийн салаа нь $v_{i}$ ба $A_{i}$ нь эхэүү зангилаанаас үүсэх язгуурын нь $A$ туслах модны $v_{i}$ навчнууд байна.

$|A_{i}|=r^{\ell _{n}-\ell _{i}}.$

Иймээс код нь префикс код тул,

$A_{i}\cap A_{j}=\varnothing ,\quad i\neq j$.

тэгэхээр,$\ell _{n}$ is $r^{\ell _{n}}$ өргөний хувьд дурын нийт салааны нийлбэр нь,

$|\bigcup _{i=1}^{n}A_{i}|=\sum _{i=1}^{n}r^{\ell _{n}-\ell _{i}}\leq r^{\ell _{n}}$

бөгөөд эндээс үүдэн.

Дурын $n$ натурал тоонуудын дараалал нь,

$\ell _{1}\leq \ell _{2}\leq \dots \leq \ell _{n}$

Ингэснээр Крафтын тэнцэтгэл бишийн хүрээнд $\ell _{i}$ урттай нууц үгтэй префикс код боловсруулж болох ба энэ нь $\ell _{n}$ өргөнтэй $r$-тын туслах модоор таслагдах болно. Эхлээд $\ell _{1}$ өргөнтэй модноос дурын зангилааг сонгож тухайн зангилааны бүх салааг устгах. Ингэснээр нийт модны $r^{-\ell _{1}}$ зангилааны бутархай нь ашиглаж буй нууц үгийн үлдэгдэл болох болно. Дараагын давталт нь $r^{-\ell _{2}}$ бутархайг $r^{-\ell _{1}}+r^{-\ell _{2}}$ модноос салгана. $m$ давталтын дараагаас,

$\sum _{i=1}^{m}r^{-\ell _{i}}$

Энэхүү бутархайг бодолтоос бүхэн устгаснаар нууц үгийн үлдсэн хэсэг нь ч нэсэн устах болно.Гэвч онолын хувьд энэхүү нийлбэр нь бүх $m<n$-ийн хувьд 1-ээс бага байна. Тэгэхээр префикс кодын урттай $\ell _{i}$ байх бүх л $n$ эх үүсвэрийн тэмдэгтийн хүрээнд боловсруулж болно.

Хоёртын модны баталгаа

Энд $T$ нь 2-тын мод гэвэл $T'$ нь $T$ модны нэг хүүхэдтэй залгаасыг холбосон 2-тын мод юм. $T'$ -ын бүх залгаас нь нэг эсвэл хоёр хүүхэдтэй байна. $T$ -ын салаа бүр нь $T'$ -д орсон байгаа иймд

$\sum _{\ell \in \mathrm {leaves} (T)}2^{-\mathrm {depth} (\ell )}\leq \sum _{\ell \in \mathrm {leaves} (T')}2^{-\mathrm {depth} (\ell )}\;.$

Дурын сонголтын хувьд $T'$ нь одоогын залгаасын хувьд навчинд хүртлээ баруун зүүн талруугаа тогтмол хөдөлж байдаг. Энэхүү хөдөлгөөн нь нэг навчинд хүрэх магадлал нь $\ell$, бөгөөд $2^{-\mathrm {depth} (\ell )}$ байна. тэгэхээр магадлалын тархаалт нь $\langle 2^{-\mathrm {depth} (\ell )}:\ell \in \mathrm {leaves} (T')\rangle$ болно

$\sum _{\ell \in \mathrm {leaves} (T')}2^{-\mathrm {depth} (\ell )}=1\;.$

Үр дүнгийн эсрэг утгын нотолгоог дээр үзүүлэв.

Ерөнхий тохиолдлын баталгаа

S кодын хүрээнд x-ийн эсрэг функц нь доорх гэж үзвэл

$F(x)=\sum _{i=1}^{n}x^{-|s_{i}|}=\sum _{\ell =\min }^{\max }p_{\ell }\,x^{-\ell }$

$x^{-\ell }$-ийн өмнө байгаа $p_{\ell }$ нь хувьсагч $\ell$ урттай нууц үгийн ялгаатай дугаар юм. Энд min нь S-ийн хамгийн богино нууц үгийн урт ба max нь хамгийн урт нууц үгийн урт болно.

Дурын эерэг бүхэл тоо m нь S^m бүтээгдэхүүнийг m-ээр хааж байна гэж үзэх бөгөөд $s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}$-ийг агуулж байдаг бол $i_{1},i_{2},\dots ,i_{m}$ нь 1 болон n-ийн хооронд зааглагддаг. S нь цор ганц задлах боломжтой шинжтэй ба, хэрэв $s_{i_{1}}s_{i_{2}}\dots s_{i_{m}}=s_{j_{1}}s_{j_{2}}\dots s_{j_{m}}$, бол $i_{1}=j_{1},i_{2}=j_{2},\dots ,i_{m}=j_{m}$ байна. Өөрөөр хэлбэл $S^{m}$-ийн бүх хэллэг нь $S$-ийн нууц үгнүүдийн онцгой дарааллаас үүссэн байна. Иймд $S^{m}$-ийн хувьд $G(x)$ функцээс $F(x)$ үүсгэх боломжгүй юм.

$G(x)=\left(F(x)\right)^{m}=\left(\sum _{i=1}^{n}x^{-|s_{i}|}\right)^{m}=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}x^{-\left(|s_{i_{1}}|+|s_{i_{2}}|+\cdots +|s_{i_{m}}|\right)}=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}x^{-|s_{i_{1}}s_{i_{2}}\cdots s_{i_{m}}|}=\sum _{\ell =m\cdot \min }^{m\cdot \max }q_{\ell }\,x^{-\ell }\;.$

Энд $G(x)$-д байгаа $x^{-\ell }$-ийн өмнөх $q_{\ell }$ хувьсагч нь $S^{m}$-д байгаа $\ell$ уртын үгийн тоо юм. $q_{\ell }$ нь $r^{\ell }$-ээс урт байж болохгүй. Иймд дурын эерэг x нь

$\left(F(x)\right)^{m}\leq \sum _{\ell =m\cdot \min }^{m\cdot \max }r^{\ell }\,x^{-\ell }\;.$

Хэрэв x = r хэмээн орлуулсан тохиолдолд

$\left(F(r)\right)^{m}\leq m\cdot (\max -\min )+1$

Тухайн $m$ нь дурын бүхэл эерэг тоо байна. Тэнцэтгэл бишийн зүүн тал нь $m$-ийн илтгэгч зэргээр өсөх ба баруун тал нь шугаман хэлбэрээр өснө. Тэнцэтгэл биш нь $m$-ийн бүх утгын хувьд зөв байх боломж нь $F(r)\leq 1$. Иймд $F(x)$-ийн тодорхойлолт ёсоор бид дараахи тэнцэл биштэй болно.

$\sum _{i=1}^{n}r^{-\ell _{i}}=\sum _{i=1}^{n}r^{-|s_{i}|}=F(r)\leq 1\;.$

Жагсаалт

• Kraft, Leon G. (1949), A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology.

• McMillan, Brockway (1956), "Two inequalities implied by unique decipherability", IEEE Trans. Information Theory, 2 (4): 115–116, doi:10.1109/TIT.1956.1056818.