Fast adaptive coding algorithm (Q2277426)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Fast adaptive coding algorithm |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast adaptive coding algorithm |
scientific article |
Statements
Fast adaptive coding algorithm (English)
0 references
1990
0 references
This paper proposed an adaptive variable-length source coding algorithm, so-called ``frequency coding''. For any message word \(x_ 1...x_ N\) over an alphabet \(A=\{a_ 1,...,a_ n\},\) denoting \(x_{-kn-h+1}=a_ h\), \(k\geq 0\), \(1\leq h\leq n\), the encoder encodes the symbol \(x_ i\) into the first \(m(x_ i,i)\) digits of the binary code of \(Q(x_ i,i)\), concatenating the result onto previous output, where \(\ell =\lceil \log n\rceil,\) \(w=(2^ r-1)2^{\ell},\) \(m(a_ j,i)=1+r+\ell -\lfloor \log (P(a_ j,i)+1)\rfloor,\) \(Q(a_ j,i)=2\sum^{j-1}_{k=1}(P(a_ k,i)+1)+P(a_ j,i)+1,\) and P(a,i) is the number of occurrences of a in \(x_{i-w}x_{i-w+1}...x_{i-1}.\) It is proven in this paper that, for this coding algorithm, redundances are not greater than O(1) as well as time complexities of encoding and of decoding are not greater than \(O(\log^ 2 n)\).
0 references
adaptive variable-length source coding algorithm
0 references
frequency coding
0 references
redundances
0 references
time complexities
0 references