848e556b0401de08fbd53c77f64d66ff technologies-11-00132.pdf 4334c8890ad89d10a061aeedb167ea8ab5de1d5d technologies-11-00132.pdf 5db7220d6322af8396da223ec889ea890de7e5a425248f5c97c09974b47791bd technologies-11-00132.pdf Title: Fast and Efficient Entropy Coding Architectures for Massive Data Compression Subject: The compression of data is fundamental to alleviating the costs of transmitting and storing massive datasets employed in myriad fields of our society. Most compression systems employ an entropy coder in their coding pipeline to remove the redundancy of coded symbols. The entropy-coding stage needs to be efficient, to yield high compression ratios, and fast, to process large amounts of data rapidly. Despite their widespread use, entropy coders are commonly assessed for some particular scenario or coding system. This work provides a general framework to assess and optimize different entropy coders. First, the paper describes three main families of entropy coders, namely those based on variable-to-variable length codes (V2VLC), arithmetic coding (AC), and tabled asymmetric numeral systems (tANS). Then, a low-complexity architecture for the most representative coder(s) of each family is presented—more precisely, a general version of V2VLC, the MQ, M, and a fixed-length version of AC and two different implementations of tANS. These coders are evaluated under different coding conditions in terms of compression efficiency and computational throughput. The results obtained suggest that V2VLC and tANS achieve the highest compression ratios for most coding rates and that the AC coder that uses fixed-length codewords attains the highest throughput. The experimental evaluation discloses the advantages and shortcomings of each entropy-coding scheme, providing insights that may help to select this stage in forthcoming compression systems. Keywords: entropy coding; variable-to-variable length codes; arithmetic coding; asymmetric numeral systems Author: Francesc Auli-Llinas Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Tue Sep 26 13:44:12 2023 CEST ModDate: Tue Sep 26 14:25:43 2023 CEST Tagged: no UserProperties: no Suspects: no Form: none JavaScript: no Pages: 15 Encrypted: no Page size: 595.276 x 841.89 pts (A4) Page rot: 0 File size: 412777 bytes Optimized: no PDF version: 1.7 name type encoding emb sub uni object ID ------------------------------------ ----------------- ---------------- --- --- --- --------- YDNPZQ+URWPalladioL-Bold Type 1 Custom yes yes no 10 0 PTLABV+URWPalladioL-Roma Type 1 Custom yes yes no 15 0 NHFQME+URWPalladioL-Ital Type 1 Custom yes yes no 19 0 XVTVPG+TimesNewRomanPS-BoldItalicMT Type 1C WinAnsi yes yes no 37 0 SOSTRQ+CMR10 Type 1 Builtin yes yes no 59 0 SAJMVH+CMSY10 Type 1 Builtin yes yes no 63 0 PGTEGT+LiberationSerif TrueType WinAnsi yes yes yes 70 0 QKRVQD+LiberationSerif-Italic TrueType WinAnsi yes yes yes 74 0 NQSAEB+LiberationSerif-Bold TrueType WinAnsi yes yes yes 78 0 QQXUPP+PazoMath Type 1 Builtin yes yes no 89 0 TICUJH+LiberationSerif TrueType WinAnsi yes yes yes 96 0 SKLQIF+LiberationSerif-Bold TrueType WinAnsi yes yes yes 100 0 QKSNKP+LiberationSerif-Italic TrueType WinAnsi yes yes yes 104 0 QIELJB+CMMI10 Type 1 Builtin yes yes no 111 0 SKMJTH+TimesNewRomanPS-ItalicMT TrueType WinAnsi yes yes yes 121 0 UGCYHT+TimesNewRomanPSMT TrueType WinAnsi yes yes yes 125 0 VTVOAB+LiberationSerif-Italic TrueType WinAnsi yes yes yes 138 0 LDCUFL+LiberationSerif-Bold TrueType WinAnsi yes yes yes 142 0 OWACST+LiberationSerif TrueType WinAnsi yes yes yes 146 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 159 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 167 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 172 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 180 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 185 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 194 0 ZSIAJZ+NimbusSanL-Regu Type 1 Custom yes yes no 199 0 Jhove (Rel. 1.22.1, 2019-04-17) Date: 2023-10-03 02:29:11 CEST RepresentationInformation: technologies-11-00132.pdf ReportingModule: PDF-hul, Rel. 1.12.1 (2019-04-17) LastModified: 2023-10-02 18:56:06 CEST Size: 412777 Format: PDF Version: 1.7 Status: Well-Formed and valid SignatureMatches: PDF-hul MIMEtype: application/pdf PDFMetadata: Objects: 392 FreeObjects: 1 IncrementalUpdates: 0 DocumentCatalog: PageLayout: SinglePage PageMode: UseNone Outlines: Item: Title: Introduction Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@262b2c86 Item: Title: Materials and Methods Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@371a67ec Children: Item: Title: Variable-to-Variable Length Codes (V2VLC) Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@5ed828d Item: Title: Arithmetic Coding (AC) Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@50d0686 Item: Title: Tabled Asymmetric Numeral Systems (tANS) Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@7a3d45bd Item: Title: Results Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@1e7c7811 Children: Item: Title: Data and Metrics Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@77ec78b9 Item: Title: Tests Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@1a3869f4 Item: Title: Discussion Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@a38d7a3 Item: Title: References Destination: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject@77f99a05 Info: Title: Fast and Efficient Entropy Coding Architectures for Massive Data Compression Author: Francesc Auli-Llinas Subject: The compression of data is fundamental to alleviating the costs of transmitting and storing massive datasets employed in myriad fields of our society. Most compression systems employ an entropy coder in their coding pipeline to remove the redundancy of coded symbols. The entropy-coding stage needs to be efficient, to yield high compression ratios, and fast, to process large amounts of data rapidly. Despite their widespread use, entropy coders are commonly assessed for some particular scenario or coding system. This work provides a general framework to assess and optimize different entropy coders. First, the paper describes three main families of entropy coders, namely those based on variable-to-variable length codes (V2VLC), arithmetic coding (AC), and tabled asymmetric numeral systems (tANS). Then, a low-complexity architecture for the most representative coder(s) of each family is presented more precisely, a general version of V2VLC, the MQ, M, and a fixed-length version of AC and two different implementations of tANS. These coders are evaluated under different coding conditions in terms of compression efficiency and computational throughput. The results obtained suggest that V2VLC and tANS achieve the highest compression ratios for most coding rates and that the AC coder that uses fixed-length codewords attains the highest throughput. The experimental evaluation discloses the advantages and shortcomings of each entropy-coding scheme, providing insights that may help to select this stage in forthcoming compression systems. Keywords: entropy coding; variable-to-variable length codes; arithmetic coding; asymmetric numeral systems Creator: LaTeX with hyperref Producer: pdfTeX-1.40.21 CreationDate: Tue Sep 26 13:44:12 CEST 2023 ModDate: Tue Sep 26 14:25:43 CEST 2023 ID: 0xf0b252d8fd88ba887263bf9d9c50f58a, 0xf0b252d8fd88ba887263bf9d9c50f58a Filters: FilterPipeline: FlateDecode Fonts: Type1: Font: BaseFont: NHFQME+URWPalladioL-Ital FontSubset: true FirstChar: 2 LastChar: 122 FontDescriptor: FontName: NHFQME+URWPalladioL-Ital Flags: Symbolic FontBBox: -170, -305, 1010, 941 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: QQXUPP+PazoMath FontSubset: true FirstChar: 229 LastChar: 229 FontDescriptor: FontName: QQXUPP+PazoMath Flags: Symbolic FontBBox: -40, -283, 878, 946 FontFile: true Font: BaseFont: YDNPZQ+URWPalladioL-Bold FontSubset: true FirstChar: 2 LastChar: 121 FontDescriptor: FontName: YDNPZQ+URWPalladioL-Bold Flags: Symbolic FontBBox: -152, -301, 1000, 935 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: SOSTRQ+CMR10 FontSubset: true FirstChar: 40 LastChar: 93 FontDescriptor: FontName: SOSTRQ+CMR10 Flags: Symbolic FontBBox: -40, -250, 1009, 750 FontFile: true Font: BaseFont: PTLABV+URWPalladioL-Roma FontSubset: true FirstChar: 2 LastChar: 242 FontDescriptor: FontName: PTLABV+URWPalladioL-Roma Flags: Symbolic FontBBox: -166, -283, 1021, 943 FontFile: true EncodingDictionary: Differences: true Font: BaseFont: SAJMVH+CMSY10 FontSubset: true FirstChar: 0 LastChar: 106 FontDescriptor: FontName: SAJMVH+CMSY10 Flags: Symbolic FontBBox: -29, -960, 1116, 775 FontFile: true Font: BaseFont: QIELJB+CMMI10 FontSubset: true FirstChar: 62 LastChar: 62 FontDescriptor: FontName: QIELJB+CMMI10 Flags: Symbolic FontBBox: -32, -250, 1048, 750 FontFile: true Pages: Page: Sequence: 1 Annotations: Annotation: Subtype: Link Rect: 50, 281, 152, 290 Annotation: Subtype: Link Rect: 34, 269, 103, 278 Annotation: Subtype: Link Rect: 34, 164, 96, 186 Annotation: Subtype: Link Rect: 126, 90, 154, 99 Annotation: Subtype: Link Rect: 34, 78, 147, 87 Annotation: Subtype: Link Rect: 34, 756, 179, 792 Annotation: Subtype: Link Rect: 515, 756, 560, 792 Annotation: Subtype: Link Rect: 130, 663, 141, 674 Annotation: Subtype: Link Rect: 310, 208, 317, 217 ActionDest: 201 Annotation: Subtype: Link Rect: 317, 208, 324, 217 ActionDest: 201 Annotation: Subtype: Link Rect: 453, 170, 459, 179 ActionDest: 201 Annotation: Subtype: Link Rect: 196, 145, 203, 154 ActionDest: 201 Annotation: Subtype: Link Rect: 206, 145, 213, 154 ActionDest: 201 Annotation: Subtype: Link Rect: 347, 107, 354, 116 ActionDest: 201 Annotation: Subtype: Link Rect: 124, 17, 293, 28 Annotation: Subtype: Link Rect: 392, 17, 560, 28 Annotation: Subtype: Link Rect: 34, 343, 87, 362 Page: Sequence: 2 Annotations: Annotation: Subtype: Link Rect: 225, 723, 232, 732 ActionDest: 201 Annotation: Subtype: Link Rect: 235, 723, 247, 732 ActionDest: 201 Annotation: Subtype: Link Rect: 494, 710, 506, 719 ActionDest: 201 Annotation: Subtype: Link Rect: 364, 698, 376, 707 ActionDest: 201 Annotation: Subtype: Link Rect: 377, 698, 389, 707 ActionDest: 201 Annotation: Subtype: Link Rect: 195, 648, 207, 657 ActionDest: 201 Annotation: Subtype: Link Rect: 210, 648, 222, 657 ActionDest: 201 Annotation: Subtype: Link Rect: 348, 607, 355, 619 ActionDest: 56 Annotation: Subtype: Link Rect: 247, 560, 259, 569 ActionDest: 201 Annotation: Subtype: Link Rect: 260, 560, 272, 569 ActionDest: 201 Annotation: Subtype: Link Rect: 210, 279, 222, 288 ActionDest: 201 Annotation: Subtype: Link Rect: 222, 279, 234, 288 ActionDest: 201 Annotation: Subtype: Link Rect: 247, 267, 259, 275 ActionDest: 201 Annotation: Subtype: Link Rect: 531, 254, 543, 263 ActionDest: 201 Annotation: Subtype: Link Rect: 543, 254, 555, 263 ActionDest: 201 Annotation: Subtype: Link Rect: 237, 241, 249, 250 ActionDest: 201 Annotation: Subtype: Link Rect: 250, 241, 262, 250 ActionDest: 201 Annotation: Subtype: Link Rect: 356, 241, 368, 250 ActionDest: 201 Annotation: Subtype: Link Rect: 447, 241, 459, 250 ActionDest: 201 Annotation: Subtype: Link Rect: 459, 241, 471, 250 ActionDest: 204 Annotation: Subtype: Link Rect: 292, 229, 304, 238 ActionDest: 204 Annotation: Subtype: Link Rect: 307, 229, 319, 238 ActionDest: 204 Annotation: Subtype: Link Rect: 340, 216, 352, 225 ActionDest: 204 Annotation: Subtype: Link Rect: 461, 166, 473, 175 ActionDest: 204 Annotation: Subtype: Link Rect: 476, 166, 488, 175 ActionDest: 204 Annotation: Subtype: Link Rect: 320, 153, 332, 162 ActionDest: 204 Annotation: Subtype: Link Rect: 335, 153, 347, 162 ActionDest: 204 Annotation: Subtype: Link Rect: 544, 141, 556, 150 ActionDest: 204 Annotation: Subtype: Link Rect: 364, 65, 376, 75 ActionDest: 204 Annotation: Subtype: Link Rect: 379, 66, 391, 75 ActionDest: 204 Page: Sequence: 3 Annotations: Annotation: Subtype: Link Rect: 207, 723, 219, 732 ActionDest: 201 Annotation: Subtype: Link Rect: 219, 723, 231, 732 ActionDest: 204 Annotation: Subtype: Link Rect: 232, 723, 244, 732 ActionDest: 204 Annotation: Subtype: Link Rect: 492, 647, 504, 657 ActionDest: 204 Annotation: Subtype: Link Rect: 364, 610, 376, 619 ActionDest: 204 Annotation: Subtype: Link Rect: 201, 585, 213, 594 ActionDest: 204 Annotation: Subtype: Link Rect: 213, 585, 225, 594 ActionDest: 204 Annotation: Subtype: Link Rect: 423, 482, 430, 494 ActionDest: 83 Annotation: Subtype: Link Rect: 500, 457, 514, 469 ActionDest: 83 Annotation: Subtype: Link Rect: 199, 431, 214, 444 ActionDest: 108 Annotation: Subtype: Link Rect: 456, 419, 471, 431 ActionDest: 129 Annotation: Subtype: Link Rect: 551, 394, 559, 406 ActionDest: 150 Annotation: Subtype: Link Rect: 299, 227, 306, 239 ActionDest: 86 Annotation: Subtype: Link Rect: 317, 190, 324, 202 ActionDest: 86 Annotation: Subtype: Link Rect: 345, 180, 357, 189 ActionDest: 201 Annotation: Subtype: Link Rect: 322, 142, 334, 151 ActionDest: 201 Annotation: Subtype: Link Rect: 382, 127, 389, 139 ActionDest: 86 Page: Sequence: 4 Annotations: Annotation: Subtype: Link Rect: 392, 695, 399, 708 ActionDest: 86 Annotation: Subtype: Link Rect: 514, 683, 521, 695 ActionDest: 86 Annotation: Subtype: Link Rect: 360, 561, 367, 573 ActionDest: 86 Annotation: Subtype: Link Rect: 193, 60, 205, 69 ActionDest: 201 Annotation: Subtype: Link Rect: 206, 59, 218, 69 ActionDest: 204 Annotation: Subtype: Link Rect: 218, 59, 230, 69 ActionDest: 204 Annotation: Subtype: Link Rect: 231, 59, 243, 69 ActionDest: 204 Page: Sequence: 5 Annotations: Annotation: Subtype: Link Rect: 476, 708, 483, 720 ActionDest: 108 Annotation: Subtype: Link Rect: 514, 683, 521, 695 ActionDest: 86 Annotation: Subtype: Link Rect: 385, 645, 392, 657 ActionDest: 108 Annotation: Subtype: Link Rect: 212, 607, 219, 619 ActionDest: 108 Annotation: Subtype: Link Rect: 272, 261, 279, 273 ActionDest: 115 Page: Sequence: 6 Annotations: Annotation: Subtype: Link Rect: 286, 527, 298, 536 ActionDest: 204 Annotation: Subtype: Link Rect: 441, 527, 453, 536 ActionDest: 204 Annotation: Subtype: Link Rect: 543, 527, 555, 536 ActionDest: 204 Annotation: Subtype: Link Rect: 196, 515, 208, 524 ActionDest: 204 Annotation: Subtype: Link Rect: 281, 515, 293, 524 ActionDest: 204 Annotation: Subtype: Link Rect: 447, 490, 459, 499 ActionDest: 204 Annotation: Subtype: Link Rect: 283, 477, 295, 486 ActionDest: 204 Annotation: Subtype: Link Rect: 544, 464, 556, 474 ActionDest: 204 Annotation: Subtype: Link Rect: 250, 452, 262, 461 ActionDest: 204 Annotation: Subtype: Link Rect: 289, 452, 301, 461 ActionDest: 204 Annotation: Subtype: Link Rect: 331, 402, 343, 411 ActionDest: 204 Annotation: Subtype: Link Rect: 344, 402, 356, 411 ActionDest: 204 Annotation: Subtype: Link Rect: 359, 402, 371, 411 ActionDest: 207 Annotation: Subtype: Link Rect: 406, 339, 418, 348 ActionDest: 204 Annotation: Subtype: Link Rect: 258, 314, 270, 323 ActionDest: 204 Annotation: Subtype: Link Rect: 544, 205, 556, 214 ActionDest: 204 Annotation: Subtype: Link Rect: 247, 107, 254, 119 ActionDest: 129 Annotation: Subtype: Link Rect: 355, 94, 362, 106 ActionDest: 108 Page: Sequence: 7 Annotations: Annotation: Subtype: Link Rect: 196, 471, 203, 483 ActionDest: 132 Annotation: Subtype: Link Rect: 466, 396, 473, 408 ActionDest: 132 Annotation: Subtype: Link Rect: 483, 208, 490, 220 ActionDest: 132 Annotation: Subtype: Link Rect: 414, 185, 426, 194 ActionDest: 204 Annotation: Subtype: Link Rect: 209, 145, 217, 157 ActionDest: 132 Page: Sequence: 8 Annotations: Annotation: Subtype: Link Rect: 509, 695, 515, 707 ActionDest: 132 Annotation: Subtype: Link Rect: 444, 346, 451, 358 ActionDest: 132 Annotation: Subtype: Link Rect: 298, 334, 305, 346 ActionDest: 132 Annotation: Subtype: Link Rect: 221, 273, 233, 283 ActionDest: 204 Annotation: Subtype: Link Rect: 319, 246, 326, 258 ActionDest: 150 Annotation: Subtype: Link Rect: 440, 208, 447, 220 ActionDest: 108 Annotation: Subtype: Link Rect: 368, 195, 375, 208 ActionDest: 150 Annotation: Subtype: Link Rect: 552, 145, 559, 157 ActionDest: 132 Annotation: Subtype: Link Rect: 309, 133, 316, 145 ActionDest: 150 Page: Sequence: 9 Annotations: Annotation: Subtype: Link Rect: 504, 221, 511, 232 ActionDest: 86 Annotation: Subtype: Link Rect: 436, 170, 443, 182 ActionDest: 153 Annotation: Subtype: Link Rect: 479, 132, 486, 144 ActionDest: 150 Annotation: Subtype: Link Rect: 217, 120, 224, 132 ActionDest: 150 Page: Sequence: 10 Annotations: Annotation: Subtype: Link Rect: 381, 469, 388, 481 ActionDest: 153 Annotation: Subtype: Link Rect: 442, 432, 449, 444 ActionDest: 153 Annotation: Subtype: Link Rect: 509, 407, 516, 419 ActionDest: 153 Annotation: Subtype: Link Rect: 434, 139, 441, 151 ActionDest: 174 Page: Sequence: 11 Annotations: Annotation: Subtype: Link Rect: 431, 190, 437, 202 ActionDest: 188 Page: Sequence: 12 Annotations: Annotation: Subtype: Link Rect: 464, 450, 471, 462 ActionDest: 188 Annotation: Subtype: Link Rect: 376, 81, 497, 92 Page: Sequence: 13 Annotations: Annotation: Subtype: Link Rect: 393, 564, 560, 575 Annotation: Subtype: Link Rect: 56, 553, 174, 564 Annotation: Subtype: Link Rect: 520, 541, 557, 552 Annotation: Subtype: Link Rect: 427, 530, 465, 541 Annotation: Subtype: Link Rect: 317, 472, 354, 483 Annotation: Subtype: Link Rect: 360, 472, 396, 483 Annotation: Subtype: Link Rect: 117, 450, 155, 460 Annotation: Subtype: Link Rect: 276, 426, 314, 437 Annotation: Subtype: Link Rect: 99, 404, 137, 414 Annotation: Subtype: Link Rect: 258, 380, 295, 391 Annotation: Subtype: Link Rect: 59, 358, 96, 368 Annotation: Subtype: Link Rect: 426, 346, 463, 357 Annotation: Subtype: Link Rect: 278, 324, 316, 334 Annotation: Subtype: Link Rect: 221, 300, 258, 311 Annotation: Subtype: Link Rect: 265, 300, 301, 311 Annotation: Subtype: Link Rect: 302, 277, 339, 288 Annotation: Subtype: Link Rect: 345, 277, 381, 288 Annotation: Subtype: Link Rect: 344, 254, 382, 265 Annotation: Subtype: Link Rect: 196, 231, 234, 242 Annotation: Subtype: Link Rect: 131, 208, 168, 219 Annotation: Subtype: Link Rect: 413, 196, 451, 207 Annotation: Subtype: Link Rect: 118, 174, 155, 184 Annotation: Subtype: Link Rect: 484, 162, 521, 173 Annotation: Subtype: Link Rect: 362, 150, 399, 161 Annotation: Subtype: Link Rect: 131, 128, 168, 138 Annotation: Subtype: Link Rect: 59, 105, 96, 115 Annotation: Subtype: Link Rect: 118, 82, 155, 92 Annotation: Subtype: Link Rect: 167, 58, 205, 69 Page: Sequence: 14 Annotations: Annotation: Subtype: Link Rect: 117, 722, 155, 733 Annotation: Subtype: Link Rect: 452, 629, 490, 640 Annotation: Subtype: Link Rect: 59, 538, 96, 548 Annotation: Subtype: Link Rect: 163, 515, 201, 525 Annotation: Subtype: Link Rect: 118, 492, 155, 502 Annotation: Subtype: Link Rect: 300, 468, 338, 479 Annotation: Subtype: Link Rect: 187, 445, 225, 456 Annotation: Subtype: Link Rect: 481, 422, 519, 433 Annotation: Subtype: Link Rect: 228, 354, 266, 364 Annotation: Subtype: Link Rect: 472, 273, 510, 284 Annotation: Subtype: Link Rect: 117, 251, 155, 261 Annotation: Subtype: Link Rect: 59, 228, 96, 238 Annotation: Subtype: Link Rect: 520, 215, 557, 226 Annotation: Subtype: Link Rect: 255, 192, 293, 203 Annotation: Subtype: Link Rect: 95, 170, 132, 180 Annotation: Subtype: Link Rect: 349, 158, 387, 169 Annotation: Subtype: Link Rect: 328, 89, 365, 100 Annotation: Subtype: Link Rect: 492, 77, 529, 88 Page: Sequence: 15 Annotations: Annotation: Subtype: Link Rect: 163, 722, 201, 733 Annotation: Subtype: Link Rect: 59, 676, 96, 687 Checksum: f152a8e5 Type: CRC32 Checksum: 848e556b0401de08fbd53c77f64d66ff Type: MD5 Checksum: 4334c8890ad89d10a061aeedb167ea8ab5de1d5d Type: SHA-1