logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Algorytm kompresji dla wsadu FPGA w ATmega 128/2561 - sugestie?

21 Lis 2006 19:43 4082 17
REKLAMA
  • #1 3248376
    Konto nie istnieje
    Konto nie istnieje  
  • REKLAMA
  • #2 3248453
    Father
    Poziom 26  
    Posty: 681
    Pomógł: 88
    Ocena: 13
    Najłatwiej będzie chyba znaleźć przykłady kompresji/dekompresji oparte o algorytm formatu zip... nawet je gdzies miałem, ale przeszukanie dysku zajmie mi trochę czasu więc może szybciej bedzie w google...
  • #3 3248762
    JacekCz
    Poziom 42  
    Posty: 8670
    Pomógł: 760
    Ocena: 1460
    Father napisał:
    Najłatwiej będzie chyba znaleźć przykłady kompresji/dekompresji oparte o algorytm formatu zip... nawet je gdzies miałem, ale przeszukanie dysku zajmie mi trochę czasu więc może szybciej bedzie w google...


    jest API do programu 7Zip, jest bez ograniczen licencyjnych i mocnie zagęszcza.
    http://www.7-zip.org/sdk.html

    Algoryt ZIP jest patentowany, chyba tylko unzipy są dostepne.

    jest też gzip.

    ALE
    a) Na pewno ambitnie używają 32 bitów (pytanie czy nie trafisz na mniej wspieramy na AVR element),
    b) spore użycie RAM-u (szukaj o opcji _LZMA_IN_CB) i
    c) funkcje systemowe (do alokowania, odczytu z plików itd.) których na gołej atmedze nie masz.

    Być może są porty specjalnie na uP bez systemu, alokowania, io.... Kompetentnie ci doradzi ktoś, kto robił to na uP.
    Warto tego poszukać.

    Disclaimer: jest to czysto rabinistyczna dywagacja, bo nie robiłem tego.

    Teraz praktyka:
    Masz też dylemat pomiędzy rozmiarem kodu dekompresera a zyskiem z kompresji.
    Kiedyś amatorskim programem (na 8085) ściskałem rozmiar tablic, wiedząc o typowych częstościach danych. Były jakieś wyniki, a kod dekompresji to było 100-200 bajtów. Był program serwisowy który tworzył tablicę ze skompresowanym obrazem jako hex asemblera.
    (Głowny zysk to schowanie stringów przed ciekawskimi.)

    Potem zrobiłęm bardziej agresywnie, był większy zysk, ale zapomniałem że kod się zwiększył i miałem stratę.
    Jeśli z góry wiesz o częstości danych (90% zer, 2% 0x07 itd) prosty amatorski algorytm może mieć sens. Być może są gdzieś zupełnie łatwe wprowadzenia o co chodzi z kompresją. Koduje się na zmiennej długości słowa, najczęstsze najkrócej (np. 3 bity na najczęstszy znak, 11-13 bitów na najrzadszy). Robi się z tego silnie niezrównoważone drzewo binarne - nie jestem w stanie zrobić ci wykładu.

    Kojarze jak przez mgłę (to 20 lat): jakies binarne badanie bitów, jakby chodzenie po drzewie prawo-lewo, statyczna tablica char[256] do ostatecznego zdekodowania.

    (Profesjonalne kompresery poznają statystykę,są uniwersalne ale większe)
  • #4 3248835
    Konto nie istnieje
    Konto nie istnieje  
  • REKLAMA
  • Pomocny post
    #5 3249038
    bis
    Poziom 21  
    Posty: 274
    Pomógł: 54
    Ocena: 3
    Ja zrobiłem cos takiego dla systemu z ARM-em i SPARTANEM 250E. Oczywiście kompresje typu ZIP i inne takie z rozwijanym słownikiem całkowicie się nie nadają do małych procków, głównie z powodu małej ilości RAM. Próby z samym Huffmanem dawały słabe wyniki. Dodałem początkowy krok w postaci kompresji powtarzających się bloków. Potem wyznaczam kodowanie Huffmana (indywidualnie dla pliku, odpowiednia tablica jest umieszczana w skompresowanym nagłówku) W moim projekcie uzyskałem następujące wyniki (dla użycia zasobów FPGA na poziomie 70%)
    Oryginalny plik - 169216 bajtów
    Po kompresji powtarzalnych bloków - 83980 (49,6% oryginalnej wielkości)
    dalej kompresja tego Huffmanem - 56428 bajtów (33,4% oryginału)

    Do rozkompresowania potrzeba tylko kilku zmiennych i wskaźników i idealnie nadaje się do rozkompresowywania "w locie" (ja programuję szeregowo za pomocą sprzęgu SPI, na przerwaniach uzyskując kolejne słowa).

    przy implementacji kompresji wychodzą zaskakujące zależności, trochę rozbudowałem oprogramowanie aby drogą prób dochodzić do optymalnego lokalnie wyniku. Z mojej analizy wynika że jest jeszcze dużo do zrobienia w dziedzinie wyszukiwania powtarzalnych bloków ale tam juz jest problem optymalizacji (coś jak problem komiwojażera, za dużo możliwych ścieżek i brak sensownego algorytmu (szybkiego) do znalezienia prawdziwego minimum). Na razie nie mam czasu na dalsze usprawnienia, taki wynik mi wystarcza.

    bis
  • #6 3251962
    JacekCz
    Poziom 42  
    Posty: 8670
    Pomógł: 760
    Ocena: 1460
    bis napisał:
    Ja zrobiłem cos takiego dla systemu z ARM-em i SPARTANEM 250E. Oczywiście kompresje typu ZIP i inne takie z rozwijanym słownikiem całkowicie się nie nadają do małych procków, głównie z powodu małej ilości RAM. Próby z samym Huffmanem dawały słabe wyniki.

    Do rozkompresowania potrzeba tylko kilku zmiennych i wskaźników i idealnie nadaje się do rozkompresowywania "w locie" (ja programuję szeregowo za pomocą sprzęgu SPI, na przerwaniach uzyskując kolejne słowa).

    przy implementacji kompresji wychodzą zaskakujące zależności, trochę rozbudowałem oprogramowanie aby drogą prób dochodzić do optymalnego lokalnie wyniku.


    Zaciekawilo mnie to, jakbyś mógl bez szkody dla siebie czy własciciela pochwalić sie fragmentami soursów byłoby fajne.
  • #7 3252146
    Konto nie istnieje
    Konto nie istnieje  
  • #8 3252374
    JacekCz
    Poziom 42  
    Posty: 8670
    Pomógł: 760
    Ocena: 1460
    Dzięki za przypomnienie Hufmanna. To co lata temu robilem, to było bardziej podobne do Huffmana niż niepodobne.
    Przynajmniej w swojej idei. Może sie wywodziło z jakiegoś artykułu... shifty bitowe na procesorku robiły się aż do czerwoności ;-)

    O ile kompresor ma konkretne wymagania RAM, to robisz to jak rozumiem na PC (czy to tylko moje wyobrażenie?).
    Dekompresor (nie potrafie matematycznie udowodnić, nos mi mówi) ma znacznie mniejsze, z ok 256-512 bajtową tablicą stałych
  • #9 3252657
    Konto nie istnieje
    Konto nie istnieje  
  • Pomocny post
    #10 3252871
    bis
    Poziom 21  
    Posty: 274
    Pomógł: 54
    Ocena: 3
    Proponuję porzucić szukanie gotowych bibliotek do Huffmana bo z reguły ich implementacja nie jest dostosowana do wymagań typu embeded. Lepiej dorwać opis metody i zrozumieć ja to działa. Jak się troche posiedzi i pokombnuje to jednak RAMu nie potrzeba tak dużo. W kodowaniu Hufmana kody od 0-255 zamieniam na różnej długości łańcuchy bitów. Tablica dla konkretnego pliku jest wyznaczana w czasie kompresowania i dodawana do skompresowanej postaci. Z zasady kodowania najdluższy łańcuch ma 15 bitów, do każdego trzeba dołaczyć informacje o długości i wartości bajtu który koduje razem narzut jest równy 256*4 bajty = 1KB ale to jest we FLASHu. Tablica jest uporządkowana narastająco więc można ją przeszukiwać liniowo (to wynika znowu z zasady kodowania, najkrótsze łańcuchy występują najczęściej więc przeszukując liniowo zawsze uzyskamy optymalną ilość komparacji) cała moja procedura zajmuje w ramie 13 zmiennych (longi , pointery i parę bajtowych, ale to jest razem z danymi organizujacymi jeszcze dekompresję powtarzalnych elementów (np. w bitstream do XILINX jest dużo "0") i organizacją odzyskiwania zdekompresowanych bajtów metodą "bajt po bajcie" na potrzeby wysyłania na przerwaniach. Podałem kilka wskazówek jak można to zrobić. Moje oprogramowanie jest dużo bardziej rozbudowane (np. wstawianie zawartości BlockRam bezpośrednio do bitstream przed kompresowaniem bez konieczności syntezy narzędziami XILINX)i jest wykorzystywane komercyjnie wiec teraz nie udostępnię żródeł. Ale może jak znajde czas to zrobię jakieś "wycinanki".

    bis
  • REKLAMA
  • Pomocny post
    #11 3253291
    JacekCz
    Poziom 42  
    Posty: 8670
    Pomógł: 760
    Ocena: 1460
    Zdecydowanie tablica może być mniejsza. Nakładając dodatkowe założenia zdroworosądkowe, np.
    a) prawdopodobniestwa wartości nie zależą od konkretnego wsadu, lecz od 'średniego wsadu'. Wprawdzie zysk mniejszy ale prostsze. Konkretne prawdopodobniestwa w dekompresorze chyba nie są już potrzebne.
    b) jakieś sortowanie
    c)drzewo jako tablica, w jakiś częsciach 16/32/64 czy jakoś tak pozwala nie posiadac typowych dla drzew wskażników. Bit za bitem prawo/lewo.

    Na pewno sie da mniejsze.
  • #12 3259761
    Konto nie istnieje
    Konto nie istnieje  
  • REKLAMA
  • Pomocny post
    #13 3260086
    bis
    Poziom 21  
    Posty: 274
    Pomógł: 54
    Ocena: 3
    Twoje wyobrażenie o tym algorytmie kompresji jest troche naiwne.Nie wiem z kąd czrpiesz wiedzę o kompresji Huffmana, ale wyrzuć to i znajdż coś innego (np. książkę pt. "Wprowadzenie do kompresji danych" Adama Drozdka).
    W tym kodowaniu każdemu z kodowanych znaków przypisuje się inny ciąg bitów, ale to nie oznacza że każdy z tych ciągów musi mieć inną długość. Optymalny algorytm tak dobiera te ciągi (na podstawie ich prawdopodobieństw, a w Naszym wypadku miarą tego prawdopodobieństwa jest czestotliwość bajtów w pliku), budując binarne drzewko, aby końcowy efekt kodowania był najkrótszy możliwy. Wtedy najdłuższy ciąg będzie długości 2*(log2(N))-1. Zauważ ze jest to przekodowanie z 256 kodów na podzbiór z ~32000 kodów.
    Jak to już wcześniej pisałem, dokładniejsze opracowania skupiają się na takich realizacjach algorytmu które są przydatne do kodowania w telekomunikacji (kody znakowe, wspólne tablice "średnich" częstości itd. itp). W Twoim przypadku lepiej jest dokładnie przemyśleć i zrobić to pod specyfike problemu kodowania bitstream XILINX.
    Ja wybrałem kodowanie bajtów bo na początku założyłem sobie że algorytm dekompresji musi byc mały, nie uzywać RAMU i wmiarę szybki. Nie próbowałem nawet dla innych długości (można by było go robić dla długości będących dzielnikami liczby 32 (tyle bitów liczy pojedyncze słowo programujące XILINX). Samym kodowniem Huffmana uzyskiwałem kompresję na poziomie 60%. Problem w tym że w bitstream Xilinxa "entropia" jest dosyć duża i więcej po prostu się nie uda (przynajmnieh czystym Huffmanem)

    bis
  • #14 3260242
    Konto nie istnieje
    Konto nie istnieje  
  • Pomocny post
    #15 3260420
    bis
    Poziom 21  
    Posty: 274
    Pomógł: 54
    Ocena: 3
    Proszę bardzo, (wystarcza kartka paieru i ołówek):
    0,37 - 0 1bit
    0,32 - 100 3 bity
    0,16 - 101 3 bity
    0,08 - 110 3 bity
    0,02 - 1110 4 bity
    0,01 - 1111 4 bity

    W algorytmie Huffmana nigdy nie powstanie takie drzewko jak narysowałeś
    kształt rozkładu drzwka nie zależy od prawdopodobieństwa. Prawdopodobieństwa jedynie decydują na jakich końcach lub rozwidleniach kończysz. A samo drzewko jest zawsze binarne i symetryczne ale z poodcinanymi fragmentami.

    bis

    no dobra, pomyliłem się
    0,37 - 0 1bit
    0,32 - 100 3 bity
    0,16 - 101 3 bity
    0,08 - 110 3 bity
    0,04 - 1110 4 bity
    0,02 - 11110 5 bitów
    0,01 - 11111 5 bitów
  • #16 3260463
    Konto nie istnieje
    Konto nie istnieje  
  • Pomocny post
    #17 3260495
    bis
    Poziom 21  
    Posty: 274
    Pomógł: 54
    Ocena: 3
    To dlatego że algorytm Shanona-Fano jest niemal optymalny, a dla prawdopodobieństw zblizonych do odwrotności potęg dwójki jest optymalny. Huffman jest zawsze optymalny więc w tym przypadku wynik kodowania jest nie do odróżnienia.

    bis

    Trochę odświeżyłem sobie wiedzę. rzeczywiście w pewnych realizacjach algorytmu Huffmana może powstawać takie drzeko jak narysowałeś ale te sposoby bazują na fakcie że średnia długość kodu jest niezmienna. Jak już powiedziałem bazowe opracowania nie są najlepiej dostosowane do tego zadania które opisałeś. W algorytmie Huffmana można uzyskać ten sam efekt końcowy na wiele sposobów Ja zastosowałem sposób który jednocześnie daje rozwiązanie z minimalną długością słów kodowych. Efekt końcowy jest taki sam (średnia długość słowa kodu jest niezmienna). W jednych realizacjach po prostu sumuje sie prawdopodobieństwa i porównuje w węzłach (wtedy może powstać takie drzewko jak twoje). W innych w każdym kroku sie je jeszcze sortuje i bierze te najmniejsze, wtedy powstaje ten wariant z minimalną długością. Dla uproszczenia porównań wystarcza pomnożyć prawdopodobieństwo kodu przez uzyskaną długość kodownia dla tego kodu i zsumować dla wszystkich kodów. Niezależnie od metody końcowy wynik będzie taki sam.

    Dodano po 3 [godziny] 3 [minuty]:

    Twoja uwaga nie dawała mi spokoju i zamiast nadal pisać z głowy (czyli z niczego :)) odgrzebałem żródła i literaturę i zrobiłem parę sprawdzeń na papierze. Serdecznie przepraszam wszystkich którym namieszałem tymi głupotami które wypisywałem wcześniej. W moim oprogramowaniu rzeczywiście zastosowałem kodowanie Shanona-Fano bo to pozwoliło mi na uzyskanie tej sensownej długosci słów kodujących. Moje poprzednie dywagacje o długości kodów w Huffmanie są beznadziejnie nieprawdziwe, a Huffman nie bardzo sie do tego nadaje. Ale parametry które podałem są jak najbardziej prawdziwe tyle że zamiast Huffmana trzeba wstawić Shanona-Fano w miejsce nazwy zastosowanej kompresji. Jeszcze raz bardzo przepraszam.

    bis
  • #18 3261863
    Konto nie istnieje
    Konto nie istnieje  

Podsumowanie tematu

✨ Dyskusja dotyczy problemu kompresji wsadu FPGA do mikrokontrolerów ATmega128 i ATmega2561, gdzie wsad programuje FPGA Xilinx po uruchomieniu urządzenia. Ze względu na rosnący rozmiar wsadu i ograniczoną pamięć FLASH w ATmedze128, rozważane są metody zmniejszenia rozmiaru wsadu poprzez kompresję i dekompresję w trakcie programowania FPGA. Standardowa opcja "Enable bitstream compression" nie przyniosła satysfakcjonujących rezultatów. Proponowane rozwiązania obejmują proste algorytmy kompresji binarnej, takie jak RLE, Huffman oraz kombinacje kompresji powtarzających się bloków z kodowaniem Huffmana. Wskazano, że popularne algorytmy typu ZIP, gzip czy LZMA są zbyt zasobożerne pod względem RAM i funkcji systemowych dla AVR. Implementacje Huffmana na AVR są możliwe, ale wymagają kompromisu między rozmiarem kodu dekompresora a uzyskanym stopniem kompresji. Autor testował własne implementacje Huffmana, uzyskując redukcję wsadu z około 97 kB do 70 kB, jednak kod dekompresora zajmował znaczną pamięć (ok. 3-17 kB). Dyskutowano o optymalizacji tablic kodów Huffmana, stosowaniu stałych tablic opartych na średnich statystykach wsadów oraz uproszczeniach struktury drzewa kodowego, co pozwala zmniejszyć zapotrzebowanie na RAM i uprościć dekompresję. Wymieniono także kwestie teoretyczne dotyczące długości słów kodowych w kodowaniu Huffmana i różnice względem kodowania Shannon-Fano. Ostatecznie autor planuje stosować uproszczone, stałe tablice kodów Huffmana wspólne dla wszystkich wsadów, co uprości dekompresję i pozwoli na efektywną kompresję w środowisku mikrokontrolera AVR.
Wygenerowane przez model językowy.
REKLAMA