Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917116689514496 |
|---|---|
| author | Bruno, Roberto De Prisco, Roberto Vaccaro, Ugo |
| author_facet | Bruno, Roberto De Prisco, Roberto Vaccaro, Ugo |
| contents | In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most $D$ ones, where $D$ is a given input parameter. We provide an $O(n^2D)$-time complexity algorithm for the construction of such codes, where $n$ is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11129 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications Bruno, Roberto De Prisco, Roberto Vaccaro, Ugo Information Theory Data Structures and Algorithms In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most $D$ ones, where $D$ is a given input parameter. We provide an $O(n^2D)$-time complexity algorithm for the construction of such codes, where $n$ is the number of codewords. We also describe several scenarios where the need to design these kinds of codes naturally arises. We also provide a Kraft-like inequality for the existence of (optimal) variable-length binary codes, subject to the above-described constraint on the number of 1's in each codeword. |
| title | Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications |
| topic | Information Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.11129 |