 |
Zastosowania dla nowych możliwości korekcji błędów?
Ten wątek jest przedawniony
Działy Forum » Nauka
| Napisano | Autor | Tytuł | | 25-08-2015 08:25 | Jarek Duda (1185 punktów) | Zastosowania dla nowych możliwości korekcji błędów?
 1 na 1 | Wyobraź sobie że masz kilka starych płyt CD z tym samym filmem. Te nośniki degradują z czasem, w końcu przekraczając użyty poziom korekcji błędów - wszystkie stają się nieczytelne (przynajmniej osobno). Pojawiające błędy są praktycznie losowe, więc powinna być możliwość wzięcia kilku takich silnie uszkodzonych nośników i jakby połączyć ich pozostałą zawartość informacyjną żeby wspólnie zrekonstruować zapisane dane. Inną częstą sytuacją z nieznanym nadawcy poziomem szumu jest broadcasting: podczas gdy każdy pakiet (odbiorca) może mieć inny poziom uszkodzeń, nadawca musi używać uniwersalne pakiety. Znowu chcielibyśmy żeby odbiorca był w stanie zrekonstruować adaptując się zarówno do otrzymanego podzbioru wszystkich pakietów, jak i ich poziomu uszkodzeń:  W standardowym (forward) error correction, nadwca musi wybrać poziom redundancji - czym wyższy tym mniej informacji może zapisać, ale i daje możliwość naprawienia większego poziomu uszkodzeń. Na przykład zwiększając dwukrotnie wielkość wiadomości, moglibyśmy teoretycznie naprawić jeśli co najwyżej losowe 11% bitów zostało zmienionych (0<->1) (binary symmetric channel, rate = 1-h(epsilon), entropia Shannona h(0.11) ~ 1/2). Jednak w powyższych sytuacjach nadawca nie wie jaki poziom redundancji powinien być użyty. Co więcej, konieczny poziom redundancji może być różny dla kolejnych użyć. Sytuacja z niepełną wiedzą nadawcy jest częściowo rozwiązana w popularnych tzw. en.wikipedia.org/wiki/Fountain_code" target=_blank rel=nofollow class=e>Fountain codes. Pozwalają one przygotować większy zbiór pakietów, tak żeby dowolny odpowiednio duży ich podzbiór pozwalał zrekonstruować wiadomość. Na przykład nadawca mógłby wziąć 10MB wiadomość, wyprodukować z niej 20 pakietów po 1MB, tak że dowolne 10 (ciut więcej w praktyce) pozwala odtworzyć całą wiadomość. Jednak to nie wystarczy żeby poradzić sobie z powyższymi scenariuszami, jako że nadawca nie zna tam także poziomu uszkodzeń. Pracuję ostatnio nad Joint Reconstruction Codes żeby radzić sobie z takimi sytuacjami gdy nadawca nie zna także poziomu szumu - wzmocnienie koncepcji Fountain codes żeby dodatkowo wspólnie korygować błędy. Pakiety są przygotowane żeby móc być traktowane przez odbiorcę zarówno jako dane jak i redundancja zależnie od sytuacji. Są wspólnie rekonstruowane/korygowane używając poziomu uszkodzeń (wyestymowanego a posteriori) jako jakby indywidualnego poziomu zaufania dla każdego pakietu. Preprint: arxiv.org/pdf/1505.07056 , github.com/JarekDuda/JointReconstructionCodes" target=_blank rel=nofollow class=e>podstawowa implementacja. Przykłady zastosowań - sytuacje kiedy nadawca ma ograniczoną wiedzę o ostatecznym poziomie uszkodzeń: - broadcasting: podczas gdy każdy pakiet (odbiorca) może mieć inny poziom uszkodzeń, nadawca musi przygotować uniwersalne pakiety, - nośniki danych: zapisujący zwykle nie wie jak bardzo uszkodzony będzie nośnik przy odczycie, - networking: nadawca zwykle nie zna tras poszczególnych pakietów, co może determinować poziom uszkodzeń, - watermarking: nadawca nie zna warunków które będą użyte podczas nagrywania danego np. obrazu czy filmu, - szybko zmieniające się warunki - nadawca może nie nadążać z adaptacją. Może jakieś inne aplikacje? Gdzie to rzeczywiście warto zastosować? Może słyszeliście o jakichś innych sposobach radzenia sobie z takimi sytuacjami? |
Autor wątku ma uprawnienia do usuwania wypowiedzi, jeżeli łamią regulamin Forum lub znacznie odbiegają od tematu.
 1 na 1 | Hodża (11172 punktów) | > Wyobraź sobie że masz kilka starych płyt CD z tym samym filmem. Te nośniki degradują z czasemKiedyś ponoć trwałość płyt CD była przewidywana na kilkaset lat. Nie wątpię, że i tu mamy do czynienia z tego samego rodzaju "postępem", co w przypadku żarówek  > Inną częstą sytuacją z nieznanym nadawcy poziomem szumu jest broadcasting: podczas gdy każdy pakiet> (odbiorca) może mieć inny poziom uszkodzeń, nadawca musi używać uniwersalne pakiety.> Znowu chcielibyśmy żeby odbiorca był w stanie zrekonstruować adaptując się zarówno do otrzymanego> podzbioru wszystkich pakietów, jak i ich poziomu uszkodzeń:Poruszyłeś bardzo ciekawy temat, choć nie sądzę, byś znalazł tu wielu wdzięcznych dyskutantów. Na ile mogę to ocenić według swojej bardzo skąpej w tej dziedzinie wiedzy, zdecydowanie wiesz, o czym piszesz, więc skorzystam z okazji, aby nawiązać jakąś dyskusję. Kwestia korekcji błędów to bardzo podstawowy problem, którego rozwiązanie miało kapitalne znaczenie dla niezawodności układów cyfrowych. O ile dobrze pamiętam, np. w systemach rozkazów ośmiobitowych ósmy bit był bitem sumy, sprawdzającym niejako (do pewnego stopnia) poprawność siedmiu wcześniejszych. Wydawać by się mogło, że transmisja danych w obwodach elektronicznych jest bliska matematycznemu ideałowi; tak wszakże nie jest i istnieją np. specjalistyczne programy, które sczytują szum nieustannie obecny w obwodach komputera, rzecz niebagatelna zważywszy na to, że wygenerowanie dajmy na to liczb faktycznie (a nie psudo-) losowych stanowi nie lada problem i niezmiernie ważny element wielu programów testujących rozmaite teorie czy modele. Bez tej nieustającej korekty komputery nasze ciągle by się zawieszały i "wzbogacały" nasze teksty przypadkowymi znakami, być może nawet ten stopień komplikacji, który osiągnęły dzisiejsze laptopy nie byłby bez tego w ogóle osiągalny. > Może słyszeliście o jakichś innych sposobach radzenia sobie z takimi sytuacjami?Słyszałem ogólnie o różnych technikach filtrowania, co ciekawe, to zagadnienie zahacza również o kryptologię, gdyż liczne techniki szyfrowania danych mają za zadanie m.in. upodobnienie sygnału do niepozornego szumu, rzecz niebagatelna, jeśli się chce pozostać niezauważonym na falach eteru  Osobiście interesowało mnie kiedyś z przyczyn praktycznych zagadnienie rozpoznawania tekstu przez programy skanerów, byłem niezwykle zdumiony, kiedy udało mi się zeskanować starą, pożółkłą książkę wydaną na marnej jakości papierze, z drukiem wklęsłym, który był dość miejscami niewyraźny, z bardzo niewielką liczbą literówek. Wprawdzie udało się to dopiero po kilkudziesięciu próbach dla różnych ustawień parametrów (program TWAIN), ale jednak. Dzisiejsze programy rozpoznawania tekstu są wzmocnione przez podpowiedzi kontekstowe - w przypadku niewyraźnego druku komputer podsuwa propozycję słowa najbliższego na podstawie rozpoznanych liter. Z pewnością tego rodzaju heurystyka ma swoje zastosowanie w korekcie transmisji danych o określonej charakterystyce semantycznej (jak w przypadku tekstu, ale to samo odnosi się do muzyki czy niektórych kategorii obrazów). Kiedyś zdarzyło mi się napisać prosty, acz całkiem skuteczny programik korygujący obraz starych zeskanowanych w dużej rozdzielczości zdjęć - okazuje się, że większą część zadrapań i małych plamek czy przetarć można łatwo usunąć automatycznie (rzecz jasna nie da się nic zrobić, jeśli fotografia jest bardzo zniszczona i znaczna część informacji została utracona). Natomiast co do bogatej dziedziny wiedzy, którą jest teoria transmisji sygnału, przyznaję, jestem zielony jak pietruszka na wiosnę 
Dixi et salvavi animam meam
|
|
 | 1 na 1 | Jarek Duda (1185 punktów) | Korekcja błędów czy kompresja danych to nie jest tylko informatyka. Innymi przykładami jest informacja genetyczna czy język. W języku mamy zarówno sporo redundancji, która pozwala odtworzyć przekaz mimo np. kiepskiej słyszalności. Szczególnie w naszym języku, w którym te wszystkie straszne koniugacje, deklinacje niosą sporo dodatkowej informacji o sytuacji. W związku z tym okazje się on prostszy w automatycznej analizie niż język angielski, który jest pełny wieloznaczności. Często jest w nim problem nawet z zaklasyfikowaniem słowa jako rzeczownik lub czasownik. Możemy też mówić o zawartości informacyjnej tekstu czyli kompresji. Co ciekawe zawartość informacyjna tekstu nie rośnie liniowo z jego długością, tylko z mniejszym wykładnikiem (tzw. hipoteza Hilberga, nie bardzo wiadomo jakim). Innymi słowy, kompresując dwa razy dłuższy tekst, dostaniemy mniej niż dwa razy dłuższe archiwum. Co do takiej informatycznej korekcji błędów, są trzy podstawowe podejścia: - kody blokowe, np. wysyłamy 3 identyczne kopie, a potem dekodujemy głosowaniem większościowym. Ciekawsze a jednak proste do zrozumienia jest pl.wikipedia.org/wiki/Kod_Hamminga- Low Density Parity Check (LDPC) - bardzo modne. Rozrzucamy losowo dużo bitów XORem pewnego (losowego) podzbioru bitów wiadomości. - różne dekodowania sekwencyjne standardowo dla tzw. kodów splotowych. Ustawiasz regularnie bity parzystości, np. 1 bit na bajt. Jeśli nie zgadza się przy dekodowaniu, cofasz się i próbujesz różnych poprawek - dostajesz takie drzewo korekcji. Używam tego podejścia w obecnej implementacji. Nowe możliwości o których mówię odpowiadają np. sytuacji że krąży jakaś historia i dociera do różnych ludzi w przeróżnych strzępkach informacji - każdy sobie rekonstruuje z uzyskanych przez siebie wiadomości, dla każdej musi niezależnie oszacować poziom zaufania (uszkodzeń). Szukam konkretnych zastosowań informatycznych: kiedy nadawca nie zna poziomu uszkodzeń poszczególnych pakietów (strzępki informacji), albo co gorsza różni odbiorcy mają różne poziomy uszkodzeń dla tych samych pakietów ...
|
|
| | 1 na 1 | Hodża (11172 punktów) | >Korekcja błędów czy kompresja danych to nie jest tylko informatyka.
>Innymi przykładami jest informacja genetyczna czy język.
>W języku mamy zarówno sporo redundancji, która pozwala odtworzyć przekaz mimo np. kiepskiej słyszalności. Szczególnie w naszym języku, w którym te wszystkie straszne koniugacje, deklinacje niosą sporo dodatkowej informacji o sytuacji. W związku z tym okazje się on prostszy w automatycznej analizie niż język angielski, który jest pełny wieloznaczności. Często jest w nim problem nawet z zaklasyfikowaniem słowa jako rzeczownik lub czasownik.
Język angielski jest nieporównanie bogatszy od polskiego w zakresie słownictwa, ale polski posiada właśnie tę zaletę, o której piszesz - syntaktyka niesie dużą porcję przekazu, łatwiej, jak mi się wydaje, podkreślać ważność konkretnych słów czy intencji kształtując formę gramatyczną, również wydaje się bardziej podatny na kreowanie aluzji i przekazu "drugiego rzędu" - tego sugerowanego i nie napisanego explicite. Oczywiście wszystkie te zjawiska są obecne i w angielskim, rzecz w tym, że nasza piękna mowa bardziej chyba nadaje się do przekazywania informacji subiektywnej o stanach emocji czy poglądach osoby wypowiadającej tekst, niż obiektywnej o materialnych relacjach zachodzących w obserwowanej rzeczywistości.
Każdy z języków naturalnych posiada swoje specyficzne zalety i wady, stąd wielojęzyczność jest tak ważna dla lepszego zrozumienia zjawisk społecznych, ba, bez tego w ogóle nie można myśleć o poznaniu mechanizmów kształtujących poszczególne społeczeństwa i kultury.
>Szukam konkretnych zastosowań informatycznych: kiedy nadawca nie zna poziomu uszkodzeń poszczególnych pakietów (strzępki informacji), albo co gorsza różni odbiorcy mają różne poziomy uszkodzeń dla tych samych pakietów ...
To mi trochę przypomina zabawę w "głuchy telefon". Jeśli mam rację, podejrzewam, że w jakimś stopniu badany przez Ciebie problem dotyka teorii grafów, np. znanego algorytmu znajdowania najkrótszej drogi, przy czym "najkrótsza" byłaby ważona wg poziomu zsumowanych zakłóceń.
Za mało wiem na temat konkretnych założeń, w obrębie których poszukujesz zastosowań dla również mało dla mnie zrozumiałego algorytmu, w każdym bądź razie wydaje mi się, że musisz tu uwzględnić jakieś założenia dotyczące właściwości zbioru węzłów komunikacyjnych, za pośrednictwem których dokonuje się transmisja.
Dixi et salvavi animam meam
|
|
| | | 2 na 2 | Jarek Duda (1185 punktów) | Abstrakcyjny język jest jednym z naszych głównych atutów nad zwierzętami ( choć one też potrafią tutaj zaskakiwać) - jest to narzędzie pozwalające przedstawić niezwykle skomplikowane obiekty jako proste abstrakty, znacznie wygodniejsze do operowania/przetwarzania/przekazywania. Jest czymś czym myślimy - jego konstrukcja ma silny wpływ na to jak myślimy, jakie są preferowane asocjacje, jakie zakazane (nowomowa Orwella ...). Na przykład nie wszystkie języki rozróżniają teraźniejszość od przyszłości - okazuje się że ma to istotny wpływ na mentalność ludzi odnośnie przyszłości, mierzalny np. w podejściu do oszczędzania: www.ted.co(*)lity_to_save_money?language=enwww.ted.co(*)althy_take_on_time?language=en
|
|
| | Abdullah (1241 punktów) |
> Kiedyś ponoć trwałość płyt CD była przewidywana na kilkaset lat. Nie wątpię, że i tu mamy do czynienia z tego samego rodzaju "postępem", co w przypadku żarówek Płyty tłoczone - tak. Płyty CD-R/DVD-R gdzie w grę wchodzą barwniki organiczne i nie ma warstwy ochronnej nigdy nie były reklamowane na setki lat. Może najlepsze - na góra 20. Zreszta bądźmy szczerzy twórcy płyty CD musieli ja jakoś zareklamować i te kilkaset lat może być tanich chwytem reklamowym.
|
|
| sztejkat (4743 punktów) | Przeczytałem PDF'a i nie bardzo rozumiem jaki dokładnie pomysł za tym stoi.
O ile chwytam ideę, czy chodzi o to, że kod korekcyjny dla całości jest rozproszony we wszystkich pakietach i dzięki temu pracuje się w dwu skalach: dekodowanie i korekta pakietu oraz dekodowanie i odzyskanie całości?
W Twoim tekście jest mnóstwo szczegółów, ale w żadnym miejscu nie ma łopatologicznego wyjaśnienia na czym tak naprawdę polega pomysł.
A jeśli idzie o aplikacje, no cóż, sam chyba podałeś wszystkie. W odpowiedzialnych zastosowaniach zawsze będzie się szło ścieżką potwierdzenia odbioru i retransmisji, bo tam musimy wiedzieć po stronie nadawcy, że informacja dotarła. Zostają zatem środowiska, w których ta wiedza jest nie potrzebna lub podnosi nieprzyzwoicie koszt pozyskania.
Jednak w środowiskach mocno zakłóconych doskonale sprawdza się podjęcie odpowiednich kroków na niższym poziomie niż pakiet i przeskok na widmo rozproszone, która to metoda potrafi sobie radzić z zakłóceniami w medium na poziomie bitu lepiej niż jakiekolwiek inne znane mi podejścia. Oczywiście, jak słusznie zauważasz, wymaga to pewnego oszacowania jakości połączenia i wyboru długości kodu rozpraszającego.
Niestety, ponieważ nie rozumiem idei jaka stoi za Twoim pomysłem nie mogę się wypowiedzieć bardziej szczegółowo.
Pozdrawiam,
Tomasz Sztejka
|
|
| | Jarek Duda (1185 punktów) | >Przeczytałem PDF'a i nie bardzo rozumiem jaki dokładnie pomysł za tym stoi. (...)
Ogólnie koncepcja wydaje się dość prosta - to może jeszcze raz:
W standardowej korekcji błędów (forward error correction) nadawca dodaje pewien wybrany poziom redundancji, pozwalając naprawić uszkodzenia aż do odpowiadającego poziomu szumu.
Jednak nie jest to dostępne w wielu scenariuszach jak z obrazka z pierwszego posta: nadawca może nie mieć informacji o poziomie szumu przed którym należy zabezpieczyć, albo nawet gorzej: różni odbiorcy tych samych pakietów mogą mieć różne poziomy szumu (podczas gdy są zabezpieczone przed tym samym poziomem).
JRC pozwala to naprawić dzięki:
- nadawca przygotowuje uniwersalne pakiety: które mogą być traktowane przez odbiorcę zarówno jako dane jak i redundancja, przygotowane pakiety są różne i uzupełniają się.
- odbiorca dopasowuje dekoder do rzeczywistych poziomów szumu otrzymanych pakietów. Dosłownie próbuje zgadnąć wiadomość - rozwijając drzewo jej możliwych kandydatów (sequential decoding). Jako bardziej obiecujących kandydatów traktuje tych którzy prowadzą do lepszej zgodności z otrzymanymi pakietami, używając ich poziomu szumu jako poziomu zaufania ich bitów: czym większy poziom szumu, tym większa tolerancja na przekłamanie tych bitów.
>A jeśli idzie o aplikacje, no cóż, sam chyba podałeś wszystkie. W odpowiedzialnych zastosowaniach zawsze będzie się szło ścieżką potwierdzenia odbioru i retransmisji, bo tam musimy wiedzieć po stronie nadawcy, że informacja dotarła. Zostają zatem środowiska, w których ta wiedza jest nie potrzebna lub podnosi nieprzyzwoicie koszt pozyskania.
Potwierdzenia (ani możliwości retransmisji) nie masz np. przy dość podstawowym zastosowaniu: odczytywanie nośników danych.
Też zwykle go nie ma przy brodacastingu: nadawca po prostu wysyła odpowiednio więcej pakietów, tak żeby statystycznie każdy potencjalny odbiorca prawie na pewno był w stanie odtworzyć wiadomość.
>Jednak w środowiskach mocno zakłóconych doskonale sprawdza się podjęcie odpowiednich kroków na niższym poziomie niż pakiet i przeskok na widmo rozproszone, która to metoda potrafi sobie radzić z zakłóceniami w medium na poziomie bitu lepiej niż jakiekolwiek inne znane mi podejścia. Oczywiście, jak słusznie zauważasz, wymaga to pewnego oszacowania jakości połączenia i wyboru długości kodu rozpraszającego.
Tutaj piszesz o innej: fizycznej warstwie. W cyfrowej erze w pewnym momencie musimy przetłumaczyć te ciągłe sygnały na bity i ich wiarygodność (opis szumu) - gdzie wchodzi poziom korekcji o którym piszę.
Pozdrawiam,
Jarek
|
|
| | | sztejkat (4743 punktów) | No dobrze. Z grubsza chwytam.
Gdzie zysk?
Piszesz "nadawca przygotowuje uniwersalne pakiety (...)". Czy dobrze rozumiem, że w efekcie i tak musi nadać informację z określoną, wydumaną z czegoś, redundancją? Czyli po prostu wysłać więcej ich niż teoretycznie potrzeba?
Dlaczego proponowane podejście jest skuteczniejsze od przyjęcia polityki: "wysyłam z maksymalną redundancją na jaką mnie stać"?
Czy proponowane rozwiązanie pozwala przesłać mniej danych dodatkowych i uzyskać większe poziom ich zabezpieczenia?
Jeśli idzie o zastosowanie, to masz rację, odczyt nośników danych jest tu dobrym przykładem, choć nie idealnie do końca. W końcu częścią zakłóceń przy odczycie jest losowy szum aparatury odczytowej i ponawiając odczyt kilkukrotnie można zmniejszyć jego wpływ. Ale to na marginesie.
Wydaje mi się, że tego rodzaju zastosowanie byłoby dobre. Załóżmy z życia wziętą sytuację. Co miesiąc robię sobie backup danych na 2-4 płytkach DVD. Zaglądnąć do niego potrzebuję może raz w roku, i czasem okazuje się, że część danych na ostatniej płycie nie daje się przeczytać. Wtedy oczywiście cofam się kolejny miesiąc wstecz i tak dalej, i tak dalej, aż trafię na plik dający się odczytać.
Czy Twój pomysł znalazłby sensowne zastosowanie w tym miejscu? To jest umożliwił przeczytanie danych z np. dwu, częściowo uszkodzonych kopii pliku plus dwu częściowo uszkodzonych plików kontrolnych?
Jeśli zaś idzie o warstwę fizyczną versus warstwy wyższe... Cóż, istnieje takie powiedzenie: gówno na wejściu, gówno na wyjściu. Ale oczywiście masz rację - jeżeli warstwa fizyczna jest narzucona i sobie nie radzi, z pomocą muszą przyjść protokoły korekcji.
Pozdrawiam,
Tomasz Sztejka
|
|
| | | | Jarek Duda (1185 punktów) | >Dlaczego proponowane podejście jest skuteczniejsze od przyjęcia polityki: "wysyłam z maksymalną redundancją na jaką mnie stać"?
Ponieważ redundancja kosztuje - przykładowo możemy wysłać 3 identyczne kopie (rate 1/3, mniejsza redundancja - zabezpieczenie), lub 10 (rate 1/10, większa ale i przesyłamy mniej informacji). Czyli rate to jest: ile prawdziwych bitów wiadomości odpowiada jednemu przesłanemu.
Teoretycznie (trudno się do tego zbliżyć), żeby zabezpieczyć np. przed prawdopodobieństwem eps zmiany bitu (0<->1), trzeba zwiększyć wiadomość 1/(1-h(eps)) razy, gdzie h(p) = - p lg(p) - (1-p) lg(1-p) to entropia Shannona. Innymi słowy rate = 1 - h(eps).
Przykładowo rate 1/2 (dwukrotne zwiększenie) pozwala naprawić maksymalnie poziom szumu eps=0.11.
Np. zapisując płytę z jakimś poziomem redundancji, zabezpieczasz przed szumem aż do pewnego poziomu, odpowiadającemu temu poziomowi redundancji.
JRC dodatkowo pozawala że po przekroczeniu tego poziomu szumu, możemy wziąć dwie lub więcej takie uszkodzone płyty i wspólnie zrekonstruować, np. z dwóch płyt o rate 1/2 (eps < 0.11) dostajemy odpowiednik korekcji dla rate 1/4 (eps < 0.214), czyli jesteśmy w stanie naprawić znacznie większy poziom szumu. Biorąc trzy takie płyty mamy rate 1/6 (eps < 0.265).
Analogicznie dla broadcastingu - podczas gdy każdy odbiorca może mieć inny poziom szumu (eps), w standardowej korekcji nadawca przygotowuje jeden poziom redundancji (rate), zabezpieczając przeciwko szumowi do pewnego poziomu (eps0).
Odbiorcy dla których szum okazał się poniżej (eps < eps0) będą w stanie odtworzyć pakiet. Aczkolwiek te pakiety mogły użyć mniejszego poziomu redundancji (dla eps a nie eps0) - zabezpieczamy je silniej niż było trzeba, czyli nieoptymalnie używamy kanał.
Natomiast pakiety o większym niż szumie (eps
>eps0) idą do kosza z całą zawartością - znowu marnujemy zasoby.
Dla JRC dekodujemy jakby każdy pakiet miał poziom redundancji zoptymalizowany dla danego odbiorcy (esp = eps0), mimo że różni odbiorcy tego samego pakietu mogą mieć różny poziom szumu jak na obrazku.
Odbiorca czeka na pakiety aż do momentu kiedy otrzymane wystarczą do zdekodowania. Nadawca wysyła tyle pakietów żeby każdy odbiorca prawie na pewno dostał wystarczająco wiele do rekonstrukcji.
|
|
| | Jarek Duda (1185 punktów) | Odnośnie zastosowań, dziś do mnie doszło że mogę trochę podrasować dekoder żeby pojawiły się nowe możliwości ... Mianowicie obecnie dekoder szuka najlepszego kandydata zakładając całkowicie losowe ciągi bitów dla wiadomości (Pr(0)=Pr(1)=1/2). Zamiast tego można by tam użyć jakiś model statystyczny (np. Markova) odpowiadający właściwościom konkretnych danych - ograniczając przestrzeń kandydatów, a więc i konieczną dla zdekodowania ilość informacji. Mianowicie podczas gdy ilość losowych ciągów bitów długości N to 2^N, ograniczenie do ciągów o statyce o entropii H<1 powoduje że asymptotycznie ich ilość rośnie jak 2^(NH) z tzw. asymptotic equipartition property. Daje to nowe możliwości dla kompresji danych - podczas gdy w standardowej musimy założyć pewien model statystyczny podczas kodowania, powyższa możliwość pozwala uzyskać taki sam stopień kompresji, ale wymagając znajomości modelu statystycznego tylko od dekodera. Czyli ostatecznie kodujący nie musi znać ani poziomów szumu, ani nawet własności statystycznych danych które kompresuje. Dyskusja: encode.ru/(*)ical-modelling-from-compressorJakieś pomysły na zastosowanie kompresji w której tylko dekoder potrzebuje znać model statystyczny? ps. Coś takiego robimy w języku naturalnym: nawet jeśli nadawca by produkował losowe dźwięki w głośnym środowisku, mózg odbiorcy będzie próbował wydedukować wiadomość zgodną z modelem języka: deterministycznym (gramatyka) i statystycznym (co jest bardziej prawdopodobne). Dzięki temu znacznie zmniejsza się przestrzeń możliwych wiadomości, a więc i konieczna informacja do zdeterminowania jednej z nich.
|
|
Aby pisać w tym wątku, musisz się zalogować
Zaloguj przez OpenID..
Jeżeli nie jesteś zarejestrowany/a - załóż konto..
Szukaj na Forum Przewodnik Regulamin i instrukcja obsługi Forum Kolegium Moderatorów
|
 |
|
