Ili si buku longonena za IT, ndi buku lonena za kaganizidwe ka anthu ozizira kwambiri. “Sikongowonjezera malingaliro abwino; limafotokoza mikhalidwe imene imawonjezera mwaŵi wakuchita ntchito yaikulu.”
Zikomo kwa Andrey Pakhomov chifukwa chomasulira.
Chiphunzitso Chachidziwitso chinapangidwa ndi C. E. Shannon kumapeto kwa zaka za m'ma 1940. Oyang'anira Bell Labs adanenetsa kuti amachitcha "Communication Theory" chifukwa ... ili ndi dzina lolondola kwambiri. Pazifukwa zodziwikiratu, dzina lakuti "Information Theory" limakhudza kwambiri anthu, chifukwa chake Shannon anasankha, ndipo ndilo dzina lomwe timadziwa mpaka lero. Dzinalo palokha limasonyeza kuti chiphunzitsochi chimakhudza zambiri, zomwe zimapangitsa kuti zikhale zofunikira pamene tikulowera mkati mwa nthawi ya chidziwitso. M'mutu uno, ndikhudza mfundo zingapo zazikuluzikulu za chiphunzitsochi, sindipereka umboni wokhwima, koma wodziwika bwino wazinthu zina za chiphunzitsochi, kuti mumvetsetse chomwe "Chidziwitso Chachidziwitso" chili, komwe mungachigwiritse ntchito. ndipo palibe .
Choyamba, kodi “chidziwitso” nchiyani? Shannon akufananiza zambiri ndi kusatsimikizika. Anasankha logarithm yolakwika ya kuthekera kwa chochitika ngati mulingo wochulukira wa chidziwitso chomwe mumalandira chochitika chokhala ndi kuthekera kwa p chichitika. Mwachitsanzo, ndikakuuzani kuti nyengo ku Los Angeles ndi ya chifunga, ndiye kuti p ili pafupi ndi 1, zomwe sizimatipatsa zambiri. Koma ndikanena kuti mvula igwa ku Monterey mu June, padzakhala kusatsimikizika mu uthengawu ndipo mudzakhala ndi zambiri. Chochitika chodalirika sichikhala ndi chidziwitso chilichonse, popeza chipika 1 = 0.
Tiyeni tiwone izi mwatsatanetsatane. Shannon ankakhulupirira kuti kuchuluka kwa chidziwitso kuyenera kukhala ntchito yosalekeza ya kuthekera kwa chochitika p, ndipo pazochitika zodziimira ziyenera kukhala zowonjezera - kuchuluka kwa chidziwitso chomwe chinapezedwa chifukwa cha zochitika ziwiri zodziimira ziyenera kukhala zofanana ndi kuchuluka kwa chidziwitso chomwe chinapezedwa chifukwa cha kuchitika kwa chochitika chogwirizana. Mwachitsanzo, zotsatira za mpukutu wa dayisi ndi ndalama zachitsulo nthawi zambiri zimatengedwa ngati zochitika zodziyimira pawokha. Tiyeni timasulire zomwe zili pamwambazi m'chinenero cha masamu. Ngati ine (p) ndi kuchuluka kwa chidziwitso chomwe chili mu chochitika chotheka p, ndiye kuti chochitika chophatikizana chokhala ndi zochitika ziwiri zodziyimira pawokha x zokhala ndi mwayi p1 ndi y wokhala ndi mwayi p2 timapeza.
(x ndi y ndi zochitika zodziyimira pawokha)
Iyi ndiye equation ya Cauchy yogwira ntchito, yowona kwa onse p1 ndi p2. Kuti muthane ndi equation yogwira ntchito, lingalirani izi
Kuchokera pakupitiriza kuganiziridwa kwa muyeso wa chidziwitso, zimatsatira kuti ntchito ya logarithmic ndiyo njira yokhayo yothetsera ntchito ya Cauchy equation.
M'malingaliro azidziwitso, ndizofala kutenga maziko a logarithm kukhala 2, kotero kusankha bayinare kumakhala ndi chidziwitso 1 ndendende. Chifukwa chake, chidziwitso chimayesedwa ndi chilinganizo
Tiyeni tiyime kaye ndikumvetsetsa zomwe zidachitika pamwambapa. Choyamba, sitinatanthauzire lingaliro la "chidziwitso"; tidangotanthauzira chilinganizo cha kuchuluka kwake.
Chachiŵiri, muyeso umenewu umakhala wosatsimikizirika, ndipo ngakhale kuti uli woyenerera moyenerera ku makina—mwachitsanzo, matelefoni, wailesi, wailesi yakanema, makompyuta, ndi zina zotero—siumasonyeza malingaliro achibadwa a anthu ponena za chidziŵitso.
Chachitatu, uwu ndi muyeso wachibale, zimatengera momwe chidziwitso chanu chilili. Ngati muyang'ana pa mtsinje wa "nambala zachisawawa" kuchokera ku jenereta yachisawawa, mukuganiza kuti nambala iliyonse yotsatila ndi yosadziwika, koma ngati mukudziwa ndondomeko yowerengera "nambala zachisawawa", nambala yotsatira idzadziwika, choncho sichidzadziwika. zili ndi zambiri.
Chifukwa chake tanthauzo lachidziwitso la Shannon ndiloyenera makina nthawi zambiri, koma sizikuwoneka kuti likugwirizana ndi kumvetsetsa kwamunthu kwa mawuwo. Ndicho chifukwa chake "Chiphunzitso Chachidziwitso" chiyenera kutchedwa "Communication Theory." Komabe, mochedwa kwambiri kusintha matanthauzo (omwe adapatsa chiphunzitsocho kutchuka kwake koyambirira, ndipo zomwe zimapangitsa anthu kuganiza kuti chiphunzitsochi chikugwirizana ndi "chidziwitso"), kotero tiyenera kukhala nawo, koma nthawi yomweyo muyenera kumvetsetsa bwino lomwe tanthauzo la chidziwitso cha Shannon ndi tanthauzo lake lomwe limagwiritsidwa ntchito nthawi zambiri. Zambiri za Shannon zimakhudzana ndi china chake chosiyana kwambiri, chomwe ndi kusatsimikizika.
Nazi zomwe muyenera kuziganizira mukamapereka mawu aliwonse. Kodi tanthauzo loperekedwa, monga tanthauzo lachidziwitso la Shannon, limagwirizana bwanji ndi lingaliro lanu loyambirira komanso losiyana bwanji? Palibe pafupifupi mawu omwe amawonetsa masomphenya anu am'mbuyomu a lingaliro, koma pamapeto pake, ndi mawu omwe amagwiritsidwa ntchito omwe amawonetsa tanthauzo la lingaliro, kotero kupanga chinthu mwachidziwitso chomveka bwino nthawi zonse kumayambitsa phokoso.
Ganizirani za dongosolo lomwe zilembo zake zimakhala ndi zizindikilo q zokhala ndi mwayi pi. Pamenepa pafupifupi kuchuluka kwa chidziwitso mu dongosolo (mtengo wake woyembekezeka) ndi wofanana ndi:
Izi zimatchedwa entropy of the system with probability distribution {pi}. Timagwiritsa ntchito mawu oti "entropy" chifukwa masamu omwewo amawonekera mu thermodynamics ndi statistical mechanics. Ichi ndichifukwa chake liwu loti "entropy" limapanga aura yofunikira mozungulira palokha, zomwe sizoyenera. Mpangidwe womwewo wa masamu wa notation sukutanthauza kutanthauzira kofanana kwa zizindikiro!
The entropy of the probability distribution amatenga gawo lalikulu pamalingaliro a coding. Kusagwirizana kwa Gibbs kwa magawo awiri osiyana siyana pi ndi qi ndi chimodzi mwazotsatira zofunika za chiphunzitsochi. Kotero ife tiyenera kutsimikizira izo
Umboniwo umachokera pa chithunzi chodziwikiratu, mkuyu. 13.I, zomwe zikusonyeza kuti
ndipo kufanana kumatheka kokha pamene x = 1. Tiyeni tigwiritse ntchito kusalingana pa nthawi iliyonse ya chiwerengero kuchokera kumanzere:
Ngati zilembo zamakina olumikizirana zili ndi zizindikilo za q, ndiye kutenga mwayi wofalitsa chizindikiro chilichonse qi = 1/q ndikulowa m'malo q, timapeza kuchokera ku kusalingana kwa Gibbs.
Chithunzi 13.I
Izi zikutanthauza kuti ngati mwayi wofalitsa zizindikiro zonse za q uli wofanana ndi wofanana ndi - 1 / q, ndiye kuti entropy yochuluka ndi yofanana ndi ln q, mwinamwake kusalingana kumagwira.
Pankhani ya kachidindo kapadera, tili ndi kusiyana kwa Kraft
Tsopano ngati titafotokoza pseudo-zotheka
kumene kumene = 1, yomwe ikutsatira kusiyana kwa Gibbs,
Chifukwa chake, entropy ndiyomwe imafikira pang'onopang'ono pamakhodi aliwonse amtundu ndi chizindikiro okhala ndi avareji yautali wa mawu a code L. Awa ndi malingaliro a Shannon a njira yopanda kusokoneza.
Tsopano ganizirani chiphunzitso chachikulu chokhudza malire a machitidwe oyankhulana omwe mauthenga amafalitsidwa monga mtsinje wazitsulo zodziimira komanso phokoso liripo. Zimamveka kuti mwayi wa kufalitsa kolondola kwa pang'ono ndi P> 1/2, ndipo mwayi woti mtengowo utembenuzidwe panthawi yopatsira (kulakwitsa kudzachitika) ndi wofanana ndi Q = 1 - P. Kuti tithandizire, ife lingalirani kuti zolakwikazo ndizodziyimira pawokha ndipo kuthekera kwa cholakwika kuli kofanana pagawo lililonse lotumizidwa - ndiko kuti, pali "phokoso loyera" munjira yolumikizirana.
Momwe tili ndi mitsinje yayitali ya n bits yosungidwa mu uthenga umodzi ndikuwonjezedwa kwa n -dimensional kwa kachidindo kamodzi. Tidzazindikira mtengo wa n pambuyo pake. Ganizirani za uthenga wopangidwa ndi n-bits ngati mfundo mu n-dimensional space. Popeza tili ndi malo a n-dimensional - ndipo kuphweka tidzaganiza kuti uthenga uliwonse uli ndi mwayi wofanana kuti uchitike - pali M mauthenga otheka (M adzafotokozedwanso pambuyo pake), chifukwa chake mwayi wa uthenga uliwonse wotumizidwa ndi
(wotumiza) Ndandanda 13.II
Kenako, lingalirani lingaliro la kuchuluka kwa mayendedwe. Popanda kulowa mwatsatanetsatane, kuchuluka kwa njira kumatanthauzidwa ngati kuchuluka kwa zidziwitso zomwe zitha kuperekedwa modalirika panjira yolumikizirana, poganizira kugwiritsa ntchito ma codec aluso kwambiri. Palibe kutsutsana kuti zambiri zitha kufalitsidwa kudzera mu njira yolumikizirana kuposa mphamvu zake. Izi zitha kutsimikiziridwa ndi njira ya binary symmetric (yomwe timagwiritsa ntchito ifeyo). Kuchuluka kwa njira, potumiza ma bits, kumatchulidwa ngati
kumene, monga kale, P ndiye mwayi woti palibe cholakwika chilichonse chotumizidwa. Mukatumiza n ma bits odziyimira pawokha, mphamvu ya njira imaperekedwa ndi
Ngati tili pafupi ndi mphamvu ya tchanelo, ndiye kuti tiyenera kutumiza pafupifupi kuchuluka kwa chidziwitso ichi pazizindikiro zilizonse ai, i = 1, ..., M. Poganizira kuti kuthekera kwa kupezeka kwa chizindikiro chilichonse ai ndi 1 / M, timapeza
pamene titumiza mauthenga aliwonse a M mofanana ndi zotheka ai, timakhala nawo
Ma n bits akatumizidwa, timayembekezera kuti zolakwika za nQ zichitika. M'malo mwake, pa uthenga wokhala ndi n-bits, tidzakhala ndi zolakwika pafupifupi za nQ mu uthenga womwe walandilidwa. Kwa n lalikulu, kusiyana kwachibale (kusiyana = kugawa m'lifupi,)
kugawidwa kwa chiwerengero cha zolakwika kudzakhala kocheperako ngati n kuwonjezeka.
Chifukwa chake, kuchokera kumbali yotumizira, ndimatenga uthenga ai kuti nditumize ndikujambula gawo lozungulira ndi radius.
chomwe chili chokulirapo pang'ono ndi kuchuluka kofanana ndi e2 kuposa kuchuluka koyembekezeka kwa zolakwika Q, (Chithunzi 13.II). Ngati n ndi yayikulu mokwanira, ndiye kuti pali mwayi wawung'ono wa uthenga wa bj wowonekera kumbali yolandila yomwe imapitilira gawoli. Tiyeni tijambule momwe zinthu zilili momwe ndikuwonera kuchokera pakuwona kwa wotumizira: tili ndi radii iliyonse kuchokera ku uthenga wopatsirana ai kupita ku uthenga wolandilidwa bj ndi kuthekera kwa cholakwika chofanana (kapena pafupifupi chofanana) ndi kugawa kwanthawi zonse, kufika pachimake. mu nq. Kwa e2 iliyonse, pali n yokulirapo kotero kuti mwayi woti bj kukhala kunja kwa gawo langa ndilaling'ono monga momwe mukufunira.
Tsopano tiyeni tiwone momwe zinthu ziliri kuchokera kumbali yanu (mkuyu 13.III). Kumbali yolandila pali gawo S(r) la radius yomweyo r kuzungulira malo olandilidwa bj mu n-dimensional space, kotero kuti ngati uthenga wolandilidwa bj uli mkati mwa gawo langa, ndiye kuti uthenga womwe watumizidwa ndi ine uli mkati mwanu. gawo.
Kutenga n kukula kokwanira, teremu yoyamba imatha kutengedwa ngati yaying'ono monga momwe mukufunira, kunena zochepa kuposa nambala ina d. Chifukwa chake tatero
Tsopano tiyeni tiwone momwe tingapangire nambala yosavuta yolowa m'malo kuti isungire mauthenga a M okhala ndi n bits. Popanda kudziwa momwe angapangire khodi (makhodi owongolera zolakwika anali asanapangidwe), Shannon adasankha kulemba mwachisawawa. Sinthanitsani ndalama pa chidutswa chilichonse cha n mu uthenga ndikubwereza ndondomeko ya mauthenga a M. Pazonse, nM coin flips iyenera kupangidwa, kotero ndizotheka
mtanthauzira mawu wokhala ndi kuthekera kofanana ½nM. Zoonadi, njira yowonongeka yopanga codebook imatanthawuza kuti pali kuthekera kobwerezabwereza, komanso ma code omwe adzakhala pafupi ndi wina ndi mzake ndipo motero amakhala gwero la zolakwika zomwe zingatheke. Mmodzi ayenera kutsimikizira kuti ngati izi sizichitika ndi kuthekera kwakukulu kuposa mulingo wolakwika womwe wasankhidwa, ndiye kuti n yopatsidwayo ndi yayikulu mokwanira.
Chofunikira ndichakuti Shannon adawerengera ma codebook onse kuti apeze zolakwika zapakati! Tidzagwiritsa ntchito chizindikiro Av[.] kusonyeza mtengo wapakati pa seti ya ma codebook onse omwe angakhalepo mwachisawawa. Avereji pa d yosalekeza, ndithudi, imapereka nthawi zonse, popeza kuwerengera nthawi iliyonse ndi yofanana ndi mawu ena onse mu chiwerengero,
zomwe zitha kuonjezedwa (M-1 kupita ku M)
Kwa uthenga uliwonse, powerengera ma codebook onse, kabisidwe kameneka kamadutsa muzinthu zonse zomwe zingatheke, kotero kuti kuthekera kwapakati kuti mfundo ili mu gawo ndi chiŵerengero cha voliyumu ya gawolo ku chiwerengero chonse cha danga. Voliyumu ya sphere ndi
pamene s=Q+e2 <1/2 ndi ns ayenera kukhala chiwerengero cha chiwerengero.
Nthawi yomaliza kumanja ndi yayikulu kwambiri pagululi. Choyamba, tiyeni tiyerekeze mtengo wake pogwiritsa ntchito Stirling formula for factorials. Kenako tiwona kuchepa kwa mawu omwe ali patsogolo pake, zindikirani kuti koyenekayi imawonjezeka pamene tikusunthira kumanzere, ndipo kotero tikhoza: (1) kuletsa mtengo wa chiwerengero ku chiwerengero cha kukula kwa geometric ndi (2) kulitsa kukula kwa geometric kuchokera ku mawu a ns kupita ku nambala yosawerengeka ya mawu, (3) kuwerengera kuchuluka kwa machulukidwe a geometric (muyezo wa algebra, palibe chofunikira) ndipo pamapeto pake pezani mtengo wochepetsera (pakuchuluka kokwanira. n):
Zindikirani momwe ma entropy H (ma) adawonekera pachidziwitso cha binomial. Dziwani kuti kukulitsa kwa mndandanda wa Taylor H(s)=H(Q+e2) kumapereka chiyerekezo chomwe chidapezedwa poganizira zotuluka koyamba ndikunyalanyaza zina zonse. Tsopano tiyeni tiphatikize mawu omaliza:
kumene
Zomwe tiyenera kuchita ndikusankha e2 kotero kuti e3 <e1, ndiyeno nthawi yomaliza idzakhala yaying'ono mopanda malire, bola n kukula kokwanira. Chifukwa chake, cholakwika chapakati cha PE chikhoza kupezedwa chaching'ono monga momwe chimafunira ndi kuchuluka kwa mayendedwe motsatana ndi C.
Ngati pafupifupi ma code onse ali ndi zolakwika pang'ono, ndiye kuti nambala imodzi iyenera kukhala yoyenera, chifukwa chake pali njira imodzi yoyenera yolembera. Izi ndi zotsatira zofunika zomwe Shannon adapeza - "lingaliro la Shannon la njira yaphokoso", ngakhale ziyenera kudziwidwa kuti adatsimikizira izi pamilandu yambiri kuposa njira yosavuta yofananira ya binary yomwe ndidagwiritsa ntchito. Pazochitika zambiri, mawerengedwe a masamu ndi ovuta kwambiri, koma malingaliro sali osiyana kwambiri, choncho nthawi zambiri, pogwiritsa ntchito chitsanzo cha nkhani inayake, mukhoza kuwulula tanthauzo lenileni la chiphunzitsocho.
Tiyeni tidzudzule zotsatira zake. Tabwereza mobwerezabwereza kuti: "Kwa zazikulu zokwanira n." Koma n wamkulu bwanji? Chachikulu, chachikulu kwambiri ngati mukufunadi kukhala pafupi ndi kuchuluka kwa mayendedwe ndikutsimikiza kusamutsa koyenera! Chachikulu kwambiri, kotero kuti mudzadikirira nthawi yayitali kuti mutenge uthenga wa ma bits okwanira kuti muutseke pambuyo pake. Pamenepa, kukula kwa mtanthauzira mawu wachisawawa kudzakhala kwakukulu (pambuyo pa zonse, dikishonale yotereyi siingakhoze kuyimiridwa mwachidule kusiyana ndi mndandanda wathunthu wa Mn bits, ngakhale n ndi M ndi zazikulu kwambiri)!
Panthawi imodzimodziyo, chiphunzitso chomwe chatsimikiziridwa pamwambapa sichinali chopanda tanthauzo! Zikuwonetsa kuti makina otumizira amayenera kugwiritsa ntchito ma encoding anzeru pazingwe zazitali kwambiri. Chitsanzo ndi ma satellites omwe awuluka kupyola mapulaneti akunja; Pamene akuyenda kutali ndi Dziko Lapansi ndi Dzuwa, amakakamizika kukonza zolakwika zowonjezereka mu deta: ma satelayiti ena amagwiritsa ntchito ma solar panels, omwe amapereka pafupifupi 5 W, ena amagwiritsa ntchito mphamvu za nyukiliya, zomwe zimapereka mphamvu zofanana. Mphamvu yotsika yamagetsi, kukula kochepa kwa mbale zopatsirana komanso kukula kochepa kwa mbale zolandirira Padziko Lapansi, mtunda waukulu womwe chizindikirocho chiyenera kuyenda - zonsezi zimafunikira kugwiritsa ntchito ma code okhala ndi zolakwika zambiri kuti apange njira yolumikizirana yogwira mtima.
Tiyeni tibwerere ku malo a n-dimensional omwe tidagwiritsa ntchito muumboni womwe uli pamwambapa. Pokambirana, tidawonetsa kuti pafupifupi voliyumu yonse ya gawoli imakhazikika pafupi ndi kunja - motero, ndizotsimikizika kuti chizindikiro chotumizidwa chidzakhala pafupi ndi gawo lomwe limamangidwa mozungulira chizindikiro chomwe chalandilidwa, ngakhale ndi cholumikizira. kagawo kakang'ono kozungulira kozungulira kotere. Choncho, n'zosadabwitsa kuti chizindikiro cholandiridwa, chitatha kukonza zolakwika zambiri, nQ, imakhala yoyandikana kwambiri ndi chizindikiro popanda zolakwika. Mphamvu yolumikizira yomwe takambirana kale ndiye chinsinsi chomvetsetsa chodabwitsa ichi. Dziwani kuti magawo ofanana omwe amapangidwira kukonza zolakwika ma code a Hamming saphatikizana. Kuchuluka kwa miyeso ya pafupifupi orthogonal mu danga la n-dimensional kumasonyeza chifukwa chake tingagwirizane ndi ma spheres a M mumlengalenga ndikudutsana pang'ono. Ngati tilola kuphatikizika kwakung'ono, kopanda malire, komwe kungayambitse zolakwika zochepa panthawi ya decoding, titha kupeza kuyika kolimba kwa mabwalo mumlengalenga. Hamming amatsimikizira mulingo wina wa kuwongolera zolakwika, Shannon - mwayi wochepa wolakwa, koma nthawi yomweyo kusunga kutulutsa kwenikweni mosagwirizana ndi kuthekera kwa njira yolumikizirana, yomwe ma code a Hamming sangathe kuchita.
Chiphunzitso cha chidziwitso sichimatiuza momwe tingapangire njira yabwino, koma chimalozera njira yolumikizirana bwino. Ndi chida chamtengo wapatali chomangira makina olumikizirana ndi makina, koma, monga tanenera kale, sichikugwirizana kwenikweni ndi momwe anthu amalankhulirana wina ndi mnzake. Momwe cholowa chachilengedwe chili ngati njira zolumikizirana zaukadaulo sizikudziwika, kotero sizikudziwika bwino momwe chidziwitso cha chidziwitso chimagwirira ntchito ku majini. Sitinachitire mwina koma kuyesera, ndipo ngati kupambana kumatiwonetsa chikhalidwe cha makina a chodabwitsa ichi, ndiye kuti kulephera kudzaloza ku mbali zina zofunika za chikhalidwe cha chidziwitso.