We study the redundancy of D-ary Fano source codes. We show that a novel splitting criterion allows to prove a bound on the redundancy of the resulting code which sharpens the guarantee provided by Shannon’s classical result for the case of an optimal code. In particular we show that, for any D≥ 2 and for every source distribution p= p1, ⋯, pn, there is a D-ary Fano code that satisfies the redundancy bound 1$$\begin{aligned} \overline{L} - H_D(\mathbf{p}) \le 1- p_{\min }, \end{aligned}$$L¯-HD(p)≤1-pmin, where, L¯ denotes the average codeword length, pmin= min ipi, and HD(p)=-∑i=1npilogD(pi) is the D-ary entropy of the source. The existence of D-ary Fano codes achieving such a bound had been conjectured in [ISIT2015], where, however, the construction proposed achieves the bound only for D= 2, 3, 4. In [ISIT2020], a novel construction was proposed leading to the proof that the redundancy bound in (1) above also holds for D= 5 (and some other special cases). This result was attained by a dynamic programming based algorithm with time complexity O(Dn) (per node of the codetree). Here, besides proving that the redundancy bound in (1) can be achieved, unconditionally, for every D> 3, we also significantly improve the time complexity of the algorithm building a D-ary Fano code tree achieving such a bound: We show that, for every D≥ 4, a D-ary Fano code tree satisfying (1) can be constructed by an efficient greedy procedure that has complexity O(Dlog 2n) per node of the codetree (i.e., improving from linear time to logarithmic time in n).

On the Redundancy of D-Ary Fano Codes

F. Cicalese;
2021-01-01

Abstract

We study the redundancy of D-ary Fano source codes. We show that a novel splitting criterion allows to prove a bound on the redundancy of the resulting code which sharpens the guarantee provided by Shannon’s classical result for the case of an optimal code. In particular we show that, for any D≥ 2 and for every source distribution p= p1, ⋯, pn, there is a D-ary Fano code that satisfies the redundancy bound 1$$\begin{aligned} \overline{L} - H_D(\mathbf{p}) \le 1- p_{\min }, \end{aligned}$$L¯-HD(p)≤1-pmin, where, L¯ denotes the average codeword length, pmin= min ipi, and HD(p)=-∑i=1npilogD(pi) is the D-ary entropy of the source. The existence of D-ary Fano codes achieving such a bound had been conjectured in [ISIT2015], where, however, the construction proposed achieves the bound only for D= 2, 3, 4. In [ISIT2020], a novel construction was proposed leading to the proof that the redundancy bound in (1) above also holds for D= 5 (and some other special cases). This result was attained by a dynamic programming based algorithm with time complexity O(Dn) (per node of the codetree). Here, besides proving that the redundancy bound in (1) can be achieved, unconditionally, for every D> 3, we also significantly improve the time complexity of the algorithm building a D-ary Fano code tree achieving such a bound: We show that, for every D≥ 4, a D-ary Fano code tree satisfying (1) can be constructed by an efficient greedy procedure that has complexity O(Dlog 2n) per node of the codetree (i.e., improving from linear time to logarithmic time in n).
978-3-030-67730-5
D-ary Fano codes, Redundancy, D-ary aggregations
File in questo prodotto:
File Dimensione Formato  
D-ary Fano Codes-cameraready.pdf

solo utenti autorizzati

Tipologia: Documento in Post-print
Licenza: Accesso ristretto
Dimensione 360.73 kB
Formato Adobe PDF
360.73 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1074146
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact