MÄs to izdarÄ«jÄm!
"Å Ä« kursa mÄrÄ·is ir sagatavot jÅ«s tehniskajai nÄkotnei."
Sveiki, Habr. Atcerieties brÄ«niŔķīgo rakstu (+219, 2588 grÄmatzÄ«mes, 429 tÅ«kst. lasÄ«jumi)?
TÄtad Hamings (jÄ, jÄ, paÅ”kontrole un paÅ”laboÅ”ana ) ir veselums , rakstÄ«ts, pamatojoties uz viÅa lekcijÄm. MÄs to tulkojam, jo āāvÄ«rietis izsaka savas domas.
Å Ä« ir grÄmata ne tikai par IT, tÄ ir grÄmata par neticami forÅ”u cilvÄku domÄÅ”anas stilu. āTas nav tikai pozitÄ«vas domÄÅ”anas stimuls; tas apraksta apstÄkļus, kas palielina iespÄjas paveikt lielisku darbu.
Paldies Andrejam Pahomovam par tulkojumu.
InformÄcijas teoriju 1940. gadu beigÄs izstrÄdÄja C. E. Shannon. Bell Labs vadÄ«ba uzstÄja, ka viÅÅ” to sauc par "komunikÄcijas teoriju", jo... Å”is ir daudz precÄ«zÄks nosaukums. AcÄ«mredzamu iemeslu dÄļ nosaukumam "InformÄcijas teorija" ir daudz lielÄka ietekme uz sabiedrÄ«bu, tÄpÄc Å enons to izvÄlÄjÄs, un tas ir nosaukums, ko mÄs zinÄm lÄ«dz pat Å”ai dienai. Pats nosaukums liecina, ka teorija attiecas uz informÄciju, kas padara to svarÄ«gu, jo mÄs virzÄmies dziļÄk informÄcijas laikmetÄ. Å ajÄ nodaÄ¼Ä es pieskarÅ”os vairÄkiem galvenajiem secinÄjumiem no Ŕīs teorijas, sniegÅ”u nevis stingrus, bet gan intuitÄ«vus pierÄdÄ«jumus dažiem atseviŔķiem Ŕīs teorijas noteikumiem, lai jÅ«s saprastu, kas patiesÄ«bÄ ir āInformÄcijas teorijaā, kur to var pielietot. un kur nÄ.
PirmkÄrt, kas ir āinformÄcijaā? Å enons informÄciju pielÄ«dzina nenoteiktÄ«bai. ViÅÅ” izvÄlÄjÄs notikuma varbÅ«tÄ«bas negatÄ«vo logaritmu kÄ informÄcijas kvantitatÄ«vu mÄru, ko saÅemat, kad notiek notikums ar varbÅ«tÄ«bu p. PiemÄram, ja es jums saku, ka laiks LosandželosÄ ir miglains, tad p ir tuvu 1, kas mums patieÅ”Äm nesniedz daudz informÄcijas. Bet, ja es saku, ka jÅ«nijÄ MonterejÄ lÄ«st, vÄstÄ«jumÄ bÅ«s neskaidrÄ«ba un tajÄ bÅ«s vairÄk informÄcijas. Uzticams notikums nesatur nekÄdu informÄciju, jo log 1 = 0.
ApskatÄ«sim to sÄ«kÄk. Å enons uzskatÄ«ja, ka informÄcijas kvantitatÄ«vajam mÄrÄ«jumam jÄbÅ«t notikuma p iespÄjamÄ«bas nepÄrtrauktai funkcijai, bet neatkarÄ«giem notikumiem tam jÄbÅ«t aditÄ«vam - informÄcijas apjomam, kas iegÅ«ts divu neatkarÄ«gu notikumu iestÄÅ”anÄs rezultÄtÄ, jÄbÅ«t vienÄdam ar kopÄ«ga notikuma iestÄÅ”anÄs rezultÄtÄ iegÅ«tÄs informÄcijas apjoms. PiemÄram, kauliÅu metiena un monÄtas metiena iznÄkums parasti tiek uzskatÄ«ts par neatkarÄ«giem notikumiem. PÄrtulkosim iepriekÅ” minÄto matemÄtikas valodÄ. Ja I (p) ir informÄcijas apjoms, ko satur notikums ar varbÅ«tÄ«bu p, tad kopÄjam notikumam, kas sastÄv no diviem neatkarÄ«giem notikumiem x ar varbÅ«tÄ«bu p1 un y ar varbÅ«tÄ«bu p2 mÄs iegÅ«stam
(x un y ir neatkarīgi notikumi)
Å is ir funkcionÄlais KoŔī vienÄdojums, kas attiecas uz visiem p1 un p2. Lai atrisinÄtu Å”o funkcionÄlo vienÄdojumu, pieÅemsim, ka
p1 = p2 = p,
tas dod
Ja p1 = p2 un p2 = p, tad
utt. PaplaÅ”inot Å”o procesu, izmantojot standarta metodi eksponenciÄliem, visiem racionÄlajiem skaitļiem m/n ir taisnÄ«ba
No pieÅemtÄs informÄcijas mÄra nepÄrtrauktÄ«bas izriet, ka logaritmiskÄ funkcija ir vienÄ«gais nepÄrtrauktais KoŔī funkcionÄlÄ vienÄdojuma risinÄjums.
InformÄcijas teorijÄ ir ierasts uzskatÄ«t, ka logaritma bÄze ir 2, tÄpÄc binÄrÄ izvÄle satur tieÅ”i 1 bitu informÄcijas. TÄpÄc informÄcija tiek mÄrÄ«ta pÄc formulas
PauzÄsim un sapratÄ«sim, kas notika iepriekÅ”. PirmkÄrt, mÄs nedefinÄjÄm jÄdzienu āinformÄcijaā, mÄs vienkÄrÅ”i definÄjÄm tÄs kvantitatÄ«vÄ mÄra formulu.
OtrkÄrt, Å”is pasÄkums ir pakļauts nenoteiktÄ«bai, un, lai gan tas ir pamatoti piemÄrots iekÄrtÄm, piemÄram, telefonu sistÄmÄm, radio, televÄ«zijai, datoriem utt., tas neatspoguļo normÄlu cilvÄku attieksmi pret informÄciju.
TreÅ”kÄrt, tas ir relatÄ«vs pasÄkums, tas ir atkarÄ«gs no jÅ«su paÅ”reizÄjÄ zinÄÅ”anu lÄ«meÅa. Ja skatÄties uz ānejauÅ”o skaitļuā straumi no nejauÅ”o skaitļu Ä£eneratora, jÅ«s pieÅemat, ka katrs nÄkamais skaitlis ir nenoteikts, bet, ja zinÄt ānejauÅ”o skaitļuā aprÄÄ·inÄÅ”anas formulu, nÄkamais skaitlis bÅ«s zinÄms, un tÄpÄc tas nebÅ«s zinÄms. satur informÄciju.
TÄtad Å enona informÄcijas definÄ«cija daudzos gadÄ«jumos ir piemÄrota maŔīnÄm, taÄu Ŕķiet, ka tÄ neatbilst cilvÄka izpratnei par Å”o vÄrdu. Å Ä« iemesla dÄļ āInformÄcijas teorijaā bija jÄsauc par āKomunikÄcijas teorijuā. TomÄr ir par vÄlu mainÄ«t definÄ«cijas (kas deva teorijai sÄkotnÄjo popularitÄti un kas joprojÄm liek cilvÄkiem domÄt, ka Ŕī teorija nodarbojas ar āinformÄcijuā), tÄpÄc mums ar tÄm ir jÄsadzÄ«vo, bet tajÄ paÅ”Ä laikÄ jums ir skaidri saprast, cik tÄlu Å enona informÄcijas definÄ«cija ir no tÄs parasti lietotÄs nozÄ«mes. Å enona informÄcija attiecas uz kaut ko pavisam citu, proti, nenoteiktÄ«bu.
LÅ«k, par ko padomÄt, piedÄvÄjot jebkÄdu terminoloÄ£iju. KÄ piedÄvÄtÄ definÄ«cija, piemÄram, Å enona informÄcijas definÄ«cija, saskan ar jÅ«su sÄkotnÄjo ideju un cik tÄ atŔķiras? GandrÄ«z nav neviena termina, kas precÄ«zi atspoguļotu jÅ«su iepriekÅ”Äjo redzÄjumu par jÄdzienu, bet galu galÄ tieÅ”i izmantotÄ terminoloÄ£ija atspoguļo jÄdziena nozÄ«mi, tÄpÄc kaut ko formalizÄjot, izmantojot skaidras definÄ«cijas, vienmÄr rodas zinÄms troksnis.
AplÅ«kosim sistÄmu, kuras alfabÄts sastÄv no simboliem q ar varbÅ«tÄ«bu pi. Å ajÄ gadÄ«jumÄ vidÄjais informÄcijas apjoms sistÄmÄ (tÄ paredzamÄ vÄrtÄ«ba) ir vienÄda ar:
To sauc par sistÄmas entropiju ar varbÅ«tÄ«bas sadalÄ«jumu {pi}. MÄs lietojam terminu "entropija", jo termodinamikÄ un statistiskajÄ mehÄnikÄ parÄdÄs viena un tÄ pati matemÄtiskÄ forma. TÄpÄc termins āentropijaā rada ap sevi zinÄmu svarÄ«guma auru, kas galu galÄ nav attaisnojama. Viena un tÄ pati matemÄtiskÄ apzÄ«mÄjuma forma nenozÄ«mÄ vienÄdu simbolu interpretÄciju!
KodÄÅ”anas teorijÄ lielu lomu spÄlÄ varbÅ«tÄ«bas sadalÄ«juma entropija. Viena no svarÄ«gÄkajÄm Ŕīs teorijas sekÄm ir Gibsa nevienlÄ«dzÄ«ba diviem dažÄdiem varbÅ«tÄ«bas sadalÄ«jumiem pi un qi. TÄpÄc mums tas ir jÄpierÄda
PierÄdÄ«jums ir balstÄ«ts uz acÄ«mredzamu grafiku, att. 13.I, kas to parÄda
un vienlÄ«dzÄ«ba tiek sasniegta tikai tad, ja x = 1. PiemÄrosim nevienÄdÄ«bu katram summas loceklim no kreisÄs puses:
Ja sakaru sistÄmas alfabÄts sastÄv no q simboliem, tad, Åemot katra simbola pÄrraides varbÅ«tÄ«bu qi = 1/q un aizstÄjot q, iegÅ«stam no Gibsa nevienÄdÄ«bas
AttÄls 13.I
Tas nozÄ«mÄ, ka, ja visu q simbolu pÄrsÅ«tÄ«Å”anas varbÅ«tÄ«ba ir vienÄda un vienÄda ar - 1 / q, tad maksimÄlÄ entropija ir vienÄda ar ln q, pretÄjÄ gadÄ«jumÄ nevienlÄ«dzÄ«ba pastÄv.
UnikÄli dekodÄjama koda gadÄ«jumÄ mums ir Krafta nevienÄdÄ«ba
Tagad, ja mÄs definÄjam pseidovarbÅ«tÄ«bas
kur protams = 1, kas izriet no Gibsa nevienlīdzības,
un pielietojiet nelielu algebru (atcerieties, ka K ā¤ 1, lai mÄs varÄtu atmest logaritmisko terminu un, iespÄjams, vÄlÄk nostiprinÄt nevienÄdÄ«bu), mÄs iegÅ«stam
kur L ir vidÄjais koda garums.
TÄdÄjÄdi entropija ir minimÄlÄ robeža jebkuram kodam pa simbolam ar vidÄjo koda vÄrda garumu L. Å Ä« ir Å enona teorÄma kanÄlam bez traucÄjumiem.
Tagad apsveriet galveno teorÄmu par sakaru sistÄmu ierobežojumiem, kurÄs informÄcija tiek pÄrraidÄ«ta kÄ neatkarÄ«gu bitu plÅ«sma un ir troksnis. Saprotams, ka viena bita pareizas pÄrraides iespÄjamÄ«ba ir P > 1/2, un varbÅ«tÄ«ba, ka pÄrraides laikÄ bita vÄrtÄ«ba tiks apgriezta (radÄ«sies kļūda), ir vienÄda ar Q = 1 - P. ÄrtÄ«bas labad mÄs pieÅemsim, ka kļūdas ir neatkarÄ«gas un kļūdas iespÄjamÄ«ba katram nosÅ«tÄ«tajam bitam ir vienÄda - tas ir, sakaru kanÄlÄ ir ābaltais troksnisā.
Veids, kÄ mums ir gara n bitu plÅ«sma, kas kodÄta vienÄ ziÅojumÄ, ir viena bita koda n-dimensijas paplaÅ”inÄjums. n vÄrtÄ«bu noteiksim vÄlÄk. Apsveriet ziÅojumu, kas sastÄv no n-bitiem, kÄ punktu n-dimensiju telpÄ. TÄ kÄ mums ir n-dimensionÄla telpa - un vienkÄrŔības labad pieÅemsim, ka katram ziÅojumam ir vienÄda raÅ”anÄs varbÅ«tÄ«ba - ir iespÄjami M ziÅojumi (arÄ« M tiks definÄts vÄlÄk), tÄpÄc jebkura nosÅ«tÄ«tÄ ziÅojuma varbÅ«tÄ«ba ir
(sÅ«tÄ«tÄjs)
Grafiks 13.II
TÄlÄk apsveriet ideju par kanÄla ietilpÄ«bu. Neiedziļinoties detaļÄs, kanÄla kapacitÄte tiek definÄta kÄ maksimÄlais informÄcijas apjoms, ko var droÅ”i pÄrsÅ«tÄ«t pa sakaru kanÄlu, Åemot vÄrÄ visefektÄ«vÄkÄs kodÄÅ”anas izmantoÅ”anu. Nav argumentu, ka pa saziÅas kanÄlu var pÄrraidÄ«t vairÄk informÄcijas nekÄ tÄ jauda. To var pierÄdÄ«t binÄram simetriskam kanÄlam (ko mÄs izmantojam mÅ«su gadÄ«jumÄ). KanÄla jauda, āānosÅ«tot bitus, tiek norÄdÄ«ta kÄ
kur, tÄpat kÄ iepriekÅ”, P ir kļūdas neesamÄ«bas varbÅ«tÄ«ba nevienÄ nosÅ«tÄ«tajÄ bitÄ. NosÅ«tot n neatkarÄ«gus bitus, kanÄla kapacitÄti nosaka ar
Ja esam tuvu kanÄla kapacitÄtei, tad mums ir jÄnosÅ«ta gandrÄ«z Å”Äds informÄcijas apjoms katram no simboliem ai, i = 1, ..., M. Å
emot vÄrÄ, ka katra simbola ai raÅ”anÄs varbÅ«tÄ«ba ir 1 / M, mÄs saÅemam
kad mÄs nosÅ«tÄm kÄdu no M vienÄdi iespÄjamiem ziÅojumiem ai, mums ir
Kad tiek nosÅ«tÄ«ti n biti, mÄs sagaidÄm nQ kļūdas. PraksÄ ziÅojumam, kas sastÄv no n-bitiem, saÅemtajÄ ziÅojumÄ mums bÅ«s aptuveni nQ kļūdas. Lieliem n, relatÄ«vÄ variÄcija (variation = sadalÄ«juma platums, )
kļūdu skaita sadalÄ«jums kļūs arvien Å”aurÄks, palielinoties n.
TÄtad no raidÄ«tÄja puses es Åemu ziÅojumu ai, lai nosÅ«tÄ«tu un ap to uzzÄ«mÄju sfÄru ar rÄdiusu
kas ir nedaudz lielÄks par summu, kas vienÄda ar e2, nekÄ paredzamais kļūdu skaits Q, (13.II attÄls). Ja n ir pietiekami liels, tad ir patvaļīgi maza varbÅ«tÄ«ba, ka uztvÄrÄja pusÄ parÄdÄ«sies ziÅojuma punkts bj, kas sniedzas Ärpus Ŕīs sfÄras. IeskicÄsim situÄciju, kÄdu es to redzu no raidÄ«tÄja viedokļa: mums ir jebkurÅ” rÄdiuss no nosÅ«tÄ«tÄ ziÅojuma ai lÄ«dz saÅemtajam ziÅojumam bj ar kļūdas varbÅ«tÄ«bu, kas vienÄda (vai gandrÄ«z vienÄda) ar normÄlo sadalÄ«jumu, sasniedzot maksimumu. no nQ. Jebkuram e2 ir tik liels n, ka varbÅ«tÄ«ba, ka iegÅ«tais punkts bj atrodas Ärpus manas sfÄras, ir tik maza, cik vÄlaties.
Tagad paskatÄ«simies uz Å”o paÅ”u situÄciju no jÅ«su puses (13.III att.). UztvÄrÄja pusÄ ap saÅemto punktu bj n-dimensiju telpÄ ir tÄda paÅ”a rÄdiusa r lode S(r), ka, ja saÅemtais ziÅojums bj atrodas manÄ sfÄrÄ, tad manis nosÅ«tÄ«tais ziÅojums ai atrodas jÅ«su iekÅ”ienÄ. sfÄra.
KÄ var rasties kļūda? Kļūda var rasties tÄlÄk esoÅ”ajÄ tabulÄ aprakstÄ«tajos gadÄ«jumos:
13.III attÄls
Å eit redzams, ka, ja sfÄrÄ, kas uzbÅ«vÄta ap saÅemto punktu, ir vÄl vismaz viens punkts, kas atbilst iespÄjamam nosÅ«tÄ«tam nekodÄtam ziÅojumam, tad pÄrraides laikÄ radÄs kļūda, jo nevar noteikt, kurÅ” no Å”iem ziÅojumiem tika nosÅ«tÄ«ts. NosÅ«tÄ«tais ziÅojums ir bez kļūdÄm tikai tad, ja tam atbilstoÅ”ais punkts atrodas sfÄrÄ, un dotajÄ kodÄ nav iespÄjami citi punkti, kas atrodas tajÄ paÅ”Ä sfÄrÄ.
Mums ir matemÄtisks vienÄdojums kļūdas Pe varbÅ«tÄ«bai, ja tiek nosÅ«tÄ«ts ziÅojums ai
MÄs varam izmest pirmo faktoru otrajÄ termiÅÄ, pieÅemot to kÄ 1. TÄdÄjÄdi mÄs iegÅ«stam nevienlÄ«dzÄ«bu
Acīmredzot,
sekojoŔi
atkÄrtoti pieteikties uz pÄdÄjo termiÅu labajÄ pusÄ
Å
emot n pietiekami lielu, pirmo terminu var Åemt tik mazu, cik vÄlas, teiksim, mazÄku par kÄdu skaitli d. TÄpÄc mums ir
Tagad apskatÄ«sim, kÄ mÄs varam izveidot vienkÄrÅ”u aizstÄÅ”anas kodu, lai kodÄtu M ziÅojumus, kas sastÄv no n bitiem. Nemaz nezinot, kÄ precÄ«zi izveidot kodu (kļūdu laboÅ”anas kodi vÄl nebija izgudroti), Å enona izvÄlÄjÄs nejauÅ”u kodÄÅ”anu. Apmetiet monÄtu katram no ziÅojuma n bitiem un atkÄrtojiet Å”o procesu M ziÅojumiem. KopumÄ jÄuztaisa nM monÄtu uzmetumi, tÄpÄc tas ir iespÄjams
kodu vÄrdnÄ«cas ar tÄdu paÅ”u varbÅ«tÄ«bu Ā½nM. Protams, nejauÅ”s kodu grÄmatas izveides process nozÄ«mÄ, ka pastÄv iespÄja dublÄties, kÄ arÄ« koda punkti, kas bÅ«s tuvu viens otram un tÄdÄjÄdi bÅ«s iespÄjamu kļūdu avots. JÄpierÄda, ka, ja tas nenotiek ar varbÅ«tÄ«bu, kas ir lielÄka par jebkuru mazu izvÄlÄto kļūdu lÄ«meni, tad dotais n ir pietiekami liels.
BÅ«tiskÄkais ir tas, ka Å enona aprÄÄ·inÄja visu iespÄjamo kodu grÄmatu vidÄjo vÄrtÄ«bu, lai atrastu vidÄjo kļūdu! MÄs izmantosim simbolu Av[.], lai apzÄ«mÄtu vidÄjo vÄrtÄ«bu visu iespÄjamo nejauÅ”o kodu grÄmatu kopÄ. VidÄji aprÄÄ·inot konstanti d, protams, tiek iegÅ«ta konstante, jo, lai aprÄÄ·inÄtu vidÄjo vÄrtÄ«bu, katrs termins ir tÄds pats kÄ katrs cits summas vÄrds,
kuru var palielinÄt (Mā1 iet uz M)
Katram ziÅojumam, veicot vidÄjo vÄrtÄ«bu visÄs kodu grÄmatÄs, kodÄÅ”ana tiek veikta caur visÄm iespÄjamÄm vÄrtÄ«bÄm, tÄpÄc vidÄjÄ varbÅ«tÄ«ba, ka punkts atrodas sfÄrÄ, ir sfÄras tilpuma attiecÄ«ba pret kopÄjo telpas tilpumu. SfÄras tilpums ir
kur s=Q+e2 <1/2 un ns ir jÄbÅ«t veselam skaitlim.
PÄdÄjais vÄrds labajÄ pusÄ ir lielÄkais Å”ajÄ summÄ. Vispirms novÄrtÄsim tÄ vÄrtÄ«bu, izmantojot Stirlinga formulu faktoriÄliem. PÄc tam mÄs apskatÄ«sim tÄ priekÅ”Ä esoÅ”Ä vÄrda dilstoÅ”o koeficientu, Åemiet vÄrÄ, ka Å”is koeficients palielinÄs, virzoties pa kreisi, un tÄdÄjÄdi mÄs varam: (1) ierobežot summas vÄrtÄ«bu lÄ«dz Ä£eometriskÄs progresijas summai ar Å”is sÄkotnÄjais koeficients, (2) paplaÅ”ina Ä£eometrisko progresiju no ns vÄrdiem uz bezgalÄ«gu skaitu vienumu, (3) aprÄÄ·ina bezgalÄ«gas Ä£eometriskÄs progresijas summu (standarta algebra, nekas bÅ«tisks) un visbeidzot iegÅ«st robežvÄrtÄ«bu (pietiekami lielam n):
IevÄrojiet, kÄ entropija H parÄdÄ«jÄs binomÄlajÄ identitÄtÄ. Å
emiet vÄrÄ, ka Teilora sÄrijas paplaÅ”inÄjums H(s)=H(Q+e2) dod novÄrtÄjumu, kas iegÅ«ts, Åemot vÄrÄ tikai pirmo atvasinÄjumu un ignorÄjot visus pÄrÄjos. Tagad saliksim galÄ«go izteiksmi:
kur
Mums tikai jÄizvÄlas e2 tÄ, lai e3 < e1, un tad pÄdÄjais termins bÅ«s patvaļīgi mazs, ja vien n ir pietiekami liels. LÄ«dz ar to vidÄjo PE kļūdu var iegÅ«t tik mazu, cik nepiecieÅ”ams, ja kanÄla jauda ir patvaļīgi tuvu C.
Ja visu kodu vidÄjam rÄdÄ«tÄjam ir pietiekami maza kļūda, tad vismaz vienam kodam ir jÄbÅ«t piemÄrotam, tÄtad ir vismaz viena piemÄrota kodÄÅ”anas sistÄma. Å is ir svarÄ«gs Å enona iegÅ«tais rezultÄts - "Å enona teorÄma trokÅ”Åainam kanÄlam", lai gan jÄatzÄ«mÄ, ka viÅÅ” to pierÄdÄ«ja daudz vispÄrÄ«gÄkÄ gadÄ«jumÄ nekÄ vienkÄrÅ”ajam binÄri simetriskam kanÄlam, ko izmantoju. VispÄrÄ«gajam gadÄ«jumam matemÄtiskie aprÄÄ·ini ir daudz sarežģītÄki, taÄu idejas nav tik dažÄdas, tÄpÄc ļoti bieži, izmantojot konkrÄta gadÄ«juma piemÄru, var atklÄt teorÄmas patieso nozÄ«mi.
KritizÄsim rezultÄtu. MÄs esam vairÄkkÄrt atkÄrtojuÅ”i: "Pietiekami lielai n." Bet cik liels ir n? Ä»oti, ļoti liels, ja tieÅ”Äm vÄlies bÅ«t gan tuvu kanÄla kapacitÄtei, gan bÅ«t pÄrliecinÄts par pareizu datu pÄrraidi! Faktiski tik liels, ka jums bÅ«s jÄgaida ļoti ilgi, lai uzkrÄtu pietiekami daudz bitu ziÅojumu, lai to vÄlÄk kodÄtu. Å ajÄ gadÄ«jumÄ izlases koda vÄrdnÄ«cas izmÄrs bÅ«s vienkÄrÅ”i milzÄ«gs (galu galÄ Å”Ädu vÄrdnÄ«cu nevar attÄlot Ä«sÄkÄ formÄ nekÄ visu Mn bitu pilnu sarakstu, neskatoties uz to, ka n un M ir ļoti lieli)!
Kļūdu laboÅ”anas kodi ļauj negaidÄ«t ļoti garu ziÅojumu un pÄc tam to kodÄt un dekodÄt, izmantojot ļoti lielas kodu grÄmatas, jo tie paÅ”i izvairÄs no kodu grÄmatÄm un tÄ vietÄ izmanto parastu aprÄÄ·inu. VienkÄrÅ”Ä teorijÄ Å”Ädi kodi mÄdz zaudÄt spÄju tuvoties kanÄla kapacitÄtei un joprojÄm saglabÄt zemu kļūdu lÄ«meni, taÄu, kad kods izlabo lielu skaitu kļūdu, tie darbojas labi. Citiem vÄrdiem sakot, ja kļūdu laboÅ”anai pieŔķirat daļu kanÄla jaudas, tad lielÄko daļu laika ir jÄizmanto kļūdu laboÅ”anas iespÄja, t.i., katrÄ nosÅ«tÄ«tajÄ ziÅojumÄ ir jÄizlabo liels skaits kļūdu, pretÄjÄ gadÄ«jumÄ jÅ«s iztÄrÄjat Å”o jaudu.
TajÄ paÅ”Ä laikÄ iepriekÅ” pierÄdÄ«tÄ teorÄma joprojÄm nav bezjÄdzÄ«ga! Tas parÄda, ka efektÄ«vÄm pÄrraides sistÄmÄm ir jÄizmanto gudras kodÄÅ”anas shÄmas ļoti garÄm bitu virknÄm. KÄ piemÄru var minÄt satelÄ«tus, kas lidojuÅ”i tÄlÄk par ÄrÄjÄm planÄtÄm; AttÄlinoties no Zemes un Saules, viÅi ir spiesti labot arvien jaunas kļūdas datu blokÄ: daži satelÄ«ti izmanto saules paneļus, kas nodroÅ”ina aptuveni 5 W, citi izmanto kodolenerÄ£ijas avotus, kas nodroÅ”ina aptuveni tÄdu paÅ”u jaudu. StrÄvas avota mazÄ jauda, āāmazie raidÄ«tÄju Ŕķīvju izmÄri un ierobežotie uztvÄrÄju Ŕķīvju izmÄri uz Zemes, milzÄ«gais attÄlums, kÄdÄ signÄlam jÄnobrauc ā tas viss prasa kodu ar augstu kļūdu laboÅ”anas lÄ«meni, lai izveidotu efektÄ«va komunikÄcijas sistÄma.
AtgriezÄ«simies pie n-dimensiju telpas, ko izmantojÄm iepriekÅ” minÄtajÄ pierÄdÄ«jumÄ. Apspriežot to, mÄs parÄdÄ«jÄm, ka gandrÄ«z viss sfÄras tilpums ir koncentrÄts ÄrÄjÄs virsmas tuvumÄ - lÄ«dz ar to ir gandrÄ«z droÅ”i, ka nosÅ«tÄ«tais signÄls atradÄ«sies netÄlu no tÄs sfÄras virsmas, kas uzbÅ«vÄta ap saÅemto signÄlu, pat ar relatÄ«vi mazs Å”Ädas sfÄras rÄdiuss. TÄpÄc nav pÄrsteidzoÅ”i, ka saÅemtais signÄls pÄc patvaļīgi liela kļūdu skaita nQ izlaboÅ”anas izrÄdÄs patvaļīgi tuvu signÄlam bez kļūdÄm. Saites jauda, āāpar kuru mÄs runÄjÄm iepriekÅ”, ir Ŕīs parÄdÄ«bas izpratnes atslÄga. Å emiet vÄrÄ, ka lÄ«dzÄ«gas sfÄras, kas izveidotas kļūdu laboÅ”anai Haminga kodiem, nepÄrklÄjas. Lielais gandrÄ«z ortogonÄlo izmÄru skaits n-dimensiju telpÄ parÄda, kÄpÄc mÄs varam ievietot M sfÄras telpÄ ar nelielu pÄrklÄÅ”anos. Ja pieļaujam nelielu, patvaļīgi mazu pÄrklÄÅ”anos, kas dekodÄÅ”anas laikÄ var radÄ«t tikai nelielu skaitu kļūdu, varam iegÅ«t blÄ«vu sfÄru izvietojumu telpÄ. Hamings garantÄja zinÄmu kļūdu laboÅ”anas lÄ«meni, Å enons - zemu kļūdu iespÄjamÄ«bu, bet tajÄ paÅ”Ä laikÄ faktiskÄs caurlaides saglabÄÅ”anu patvaļīgi tuvu sakaru kanÄla kapacitÄtei, ko Haminga kodi nevar izdarÄ«t.
InformÄcijas teorija nepasaka mums, kÄ izveidot efektÄ«vu sistÄmu, bet tÄ norÄda ceļu uz efektÄ«vÄm komunikÄcijas sistÄmÄm. Tas ir vÄrtÄ«gs rÄ«ks, lai izveidotu sakaru sistÄmas starp maŔīnÄm, taÄu, kÄ minÄts iepriekÅ”, tam ir maza nozÄ«me cilvÄku savstarpÄjÄ saziÅÄ. Tas, cik lielÄ mÄrÄ bioloÄ£iskÄ mantoÅ”ana ir lÄ«dzÄ«ga tehniskÄm komunikÄciju sistÄmÄm, vienkÄrÅ”i nav zinÄms, tÄpÄc paÅ”laik nav skaidrs, kÄ informÄcijas teorija attiecas uz gÄniem. Mums nav citas izvÄles, kÄ mÄÄ£inÄt, un, ja veiksme mums parÄda Ŕīs parÄdÄ«bas maŔīnveida raksturu, tad neveiksme norÄdÄ«s uz citiem nozÄ«mÄ«giem informÄcijas rakstura aspektiem.
NeatkÄpsimies pÄrÄk daudz. MÄs esam redzÄjuÅ”i, ka visÄm sÄkotnÄjÄm definÄ«cijÄm lielÄkÄ vai mazÄkÄ mÄrÄ ir jÄpauž mÅ«su sÄkotnÄjÄs pÄrliecÄ«bas bÅ«tÄ«ba, taÄu tÄm ir raksturÄ«ga zinÄma izkropļojuma pakÄpe un tÄpÄc tÄs nav piemÄrojamas. TradicionÄli tiek pieÅemts, ka galu galÄ mÅ«su izmantotÄ definÄ«cija faktiski nosaka bÅ«tÄ«bu; bet tas tikai stÄsta mums, kÄ apstrÄdÄt lietas, un nekÄdÄ veidÄ nesniedz mums nekÄdu nozÄ«mi. PostulÄcijas pieeja, kas tik ļoti iecienÄ«ta matemÄtikas aprindÄs, praksÄ atstÄj daudz ko vÄlÄties.
Tagad mÄs apskatÄ«sim IQ testu piemÄru, kur definÄ«cija ir tik apļveida, cik vÄlaties, un rezultÄtÄ tÄ ir maldinoÅ”a. Tiek izveidots tests, kam paredzÄts izmÄrÄ«t intelektu. PÄc tam tas tiek pÄrskatÄ«ts, lai tas bÅ«tu pÄc iespÄjas konsekventÄks, un pÄc tam tas tiek publicÄts un ar vienkÄrÅ”u metodi kalibrÄts tÄ, lai izmÄrÄ«tais āinteliÄ£enceā izrÄdÄ«tos normÄli sadalÄ«ts (protams, uz kalibrÄÅ”anas lÄ«knes). Visas definÄ«cijas ir atkÄrtoti jÄpÄrbauda ne tikai tad, kad tÄs tiek piedÄvÄtas pirmo reizi, bet arÄ« daudz vÄlÄk, kad tÄs tiek izmantotas izdarÄ«tajos secinÄjumos. Cik lielÄ mÄrÄ definÄ«cijas robežas ir piemÄrotas risinÄmajai problÄmai? Cik bieži vienÄ iestatÄ«jumÄ sniegtÄs definÄ«cijas tiek lietotas diezgan atŔķirÄ«gos iestatÄ«jumos? Tas notiek diezgan bieži! HumanitÄrajÄs zinÄtnÄs, ar kurÄm savÄ dzÄ«vÄ neizbÄgami saskarsies, tas notiek biežÄk.
TÄdÄjÄdi viens no Ŕīs informÄcijas teorijas prezentÄcijas mÄrÄ·iem, papildus tÄs lietderÄ«bas demonstrÄÅ”anai, bija brÄ«dinÄt par Ŕīm briesmÄm vai arÄ« parÄdÄ«t, kÄ tieÅ”i to izmantot, lai iegÅ«tu vÄlamo rezultÄtu. Jau sen ir atzÄ«mÄts, ka sÄkotnÄjÄs definÄ«cijas nosaka to, ko jÅ«s galu galÄ atrodat, daudz lielÄkÄ mÄrÄ, nekÄ Å”Ä·iet. SÄkotnÄjÄs definÄ«cijas prasa no jums lielu uzmanÄ«bu ne tikai jebkurÄ jaunÄ situÄcijÄ, bet arÄ« jomÄs, ar kurÄm jÅ«s strÄdÄjat ilgu laiku. Tas ļaus jums saprast, cik lielÄ mÄrÄ iegÅ«tie rezultÄti ir tautoloÄ£ija, nevis kaut kas noderÄ«gs.
Slavenais Edingtonas stÄsts stÄsta par cilvÄkiem, kuri makŔķerÄja jÅ«rÄ ar tÄ«klu. IzpÄtot nozvejoto zivju izmÄru, viÅi noteica minimÄlo zivju izmÄru, kas sastopams jÅ«rÄ! ViÅu secinÄjumus noteica izmantotais instruments, nevis realitÄte.
Lai varÄtu turpinÄt ...
Kas vÄlas palÄ«dzÄt ar grÄmatas tulkoÅ”anu, maketÄÅ”anu un izdoÅ”anu - rakstiet personÄ«gÄ ziÅÄ vai e-pastÄ [e-pasts aizsargÄts]
Starp citu, esam uzsÄkuÅ”i arÄ« citas forÅ”as grÄmatas tulkoÅ”anu - )
MÄs Ä«paÅ”i meklÄjam tie, kas palÄ«dzÄs tulkot . (pÄrsÅ«tÄ«Å”ana uz 10 minÅ«tÄm, pirmÄs 20 jau paÅemtas)
GrÄmatas saturs un tulkotÄs nodaļas
- Ievads zinÄtnÄ un inženierzinÄtnÄs: mÄcÄ«Å”anÄs mÄcÄ«ties (28. gada 1995. marts)
- "DigitÄlÄs (diskrÄtÄs) revolÅ«cijas pamati" (30. gada 1995. marts)
- "Datoru vÄsture ā aparatÅ«ra" (31. gada 1995. marts)
- "Datoru vÄsture ā programmatÅ«ra" (4. gada 1995. aprÄ«lis)
- "Datoru vÄsture ā lietojumprogrammas" (6. gada 1995. aprÄ«lis)
- "MÄkslÄ«gais intelekts ā I daļa" (7. gada 1995. aprÄ«lis)
- "MÄkslÄ«gais intelekts ā II daļa" (11. gada 1995. aprÄ«lis)
- "MÄkslÄ«gais intelekts III" (13. gada 1995. aprÄ«lis)
- "n-dimensiju telpa" (14. gada 1995. aprīlis)
- "KodÄÅ”anas teorija ā informÄcijas attÄlojums, I daļa" (18. gada 1995. aprÄ«lis)
- "KodÄÅ”anas teorija ā informÄcijas attÄlojums, II daļa" (20. gada 1995. aprÄ«lis)
- "Kļūdu laboŔanas kodi" (21. gada 1995. aprīlis)
- "InformÄcijas teorija" (25. gada 1995. aprÄ«lis)
- "DigitÄlie filtri, I daļa" (27. gada 1995. aprÄ«lis)
- "DigitÄlie filtri, II daļa" (28. gada 1995. aprÄ«lis)
- "DigitÄlie filtri, III daļa" (2. gada 1995. maijs)
- "DigitÄlie filtri, IV daļa" (4. gada 1995. maijs)
- "SimulÄcija, I daļa" (5. gada 1995. maijs)
- "SimulÄcija, II daļa" (9. gada 1995. maijs)
- "SimulÄcija, III daļa" (11. gada 1995. maijs)
- "Fiber Optics" (12. gada 1995. maijs)
- "DatorizÄta apmÄcÄ«ba" (16. gada 1995. maijs)
- "MatemÄtika" (18. gada 1995. maijs)
- "Kvantu mehÄnika" (19. gada 1995. maijs)
- "RadoŔums" (23.). Tulkojums:
- "Eksperti" (25. gada 1995. maijs)
- "Neuzticami dati" (26. gada 1995. maijs)
- "SistÄmu inženierija" (30. gada 1995. maijs)
- "You Get What You Measure" (1. gada 1995. jūnijs)
- (Jūnijs 2, 1995) tulkot 10 minūŔu gabalos
- Hamings, āYou and Your Researchā (6. gada 1995. jÅ«nijs).
Kas vÄlas palÄ«dzÄt ar grÄmatas tulkoÅ”anu, maketÄÅ”anu un izdoÅ”anu - rakstiet personÄ«gÄ ziÅÄ vai e-pastÄ [e-pasts aizsargÄts]
Avots: www.habr.com