Huffman Codes for BLISS Signatures » History » Version 2
« Previous -
Version 2/6
(diff) -
Next » -
Current version
Andreas Steffen, 13.12.2014 17:08
Huffman Codes for BLISS Signatures¶
- Table of contents
- Huffman Codes for BLISS Signatures
All Huffman codes are generated automatically using the bliss_huffman utility.
The data structures used are defined in bliss_huffman_code.h
BLISS-I Signature Encoding¶
Design Parameters
/* * Design: sigma = 215 * * i p_z1[i] * 0 0.7662277087816564 0 .. 256 * 1 0.2165251006508514 256 .. 512 * 2 0.0168930510015114 512 .. 768 * 3 0.0003522302274478 768 .. 1024 * 4 0.0000019067136680 1024 .. 1280 * 5 0.0000000026239598 1280 .. 1536 * 6 0.0000000000009052 1536 .. 1792 * 7 0.0000000000000001 1792 .. 2047 * * k p_z2[k] dx = 1024 * -1 0.0086781953089156 -1535.5 .. -511.5 * 0 0.9826436093821688 -511.5 .. 511.5 * 1 0.0086781953089156 511.5 .. 1535.5 * * (i, k) p * (0,-1) 0.0066494737079101 * (0, 0) 0.7529287613658361 * (0, 1) 0.0066494737079101 * * (1,-1) 0.0018790471127307 * (1, 0) 0.2127670064253900 * (1, 1) 0.0018790471127307 * * (2,-1) 0.0001466011959546 * (2, 0) 0.0165998486096022 * (2, 1) 0.0001466011959546 * * (3,-1) 0.0000030567227075 * (3, 0) 0.0003461167820328 * (3, 1) 0.0000030567227075 * * (4,-1) 0.0000000165468336 * (4, 0) 0.0000018736200007 * (4, 1) 0.0000000165468336 * * (5,-1) 0.0000000000227712 * (5, 0) 0.0000000025784174 * (5, 1) 0.0000000000227712 * * (6,-1) 0.0000000000000079 * (6, 0) 0.0000000000008895 * (6, 1) 0.0000000000000079 * * (7,-1) 0.0000000000000000 * (7, 0) 0.0000000000000001 * (7, 1) 0.0000000000000000 * * p_sum 0.9999999999999998 * * entropy = 1.0195 bits/tuple (521 bits) */
Decoding Tree
#include "bliss_huffman_code.h"
static bliss_huffman_code_node_t nodes[] = {
{ 1, 2, -1 }, /* 0: */
{ -1, -1, 1 }, /* 1: (0, 0) 1 bit */
{ 3, 4, -1 }, /* 2: */
{ -1, -1, 4 }, /* 3: (1, 0) 2 bits */
{ 5, 46, -1 }, /* 4: */
{ 6, 45, -1 }, /* 5: */
{ 7, 8, -1 }, /* 6: */
{ -1, -1, 0 }, /* 7: (0,-1) 5 bits */
{ 9, 44, -1 }, /* 8: */
{ 10, 11, -1 }, /* 9: */
{ -1, -1, 3 }, /* 10: (1,-1) 7 bits */
{ 12, 13, -1 }, /* 11: */
{ -1, -1, 10 }, /* 12: (3, 0) 8 bits */
{ 14, 29, -1 }, /* 13: */
{ 15, 22, -1 }, /* 14: */
{ 16, 19, -1 }, /* 15: */
{ 17, 18, -1 }, /* 16: */
{ -1, -1, 8 }, /* 17: (2, 1) 12 bits */
{ -1, -1, 6 }, /* 18: (2,-1) 12 bits */
{ 20, 21, -1 }, /* 19: */
{ -1, -1, 11 }, /* 20: (3, 1) 12 bits */
{ -1, -1, 9 }, /* 21: (3,-1) 12 bits */
{ 23, 26, -1 }, /* 22: */
{ 24, 25, -1 }, /* 23: */
{ -1, -1, 13 }, /* 24: (4, 0) 12 bits */
{ -1, -1, 14 }, /* 25: (4, 1) 12 bits */
{ 27, 28, -1 }, /* 26: */
{ -1, -1, 12 }, /* 27: (4,-1) 12 bits */
{ -1, -1, 16 }, /* 28: (5, 0) 12 bits */
{ 30, 37, -1 }, /* 29: */
{ 31, 34, -1 }, /* 30: */
{ 32, 33, -1 }, /* 31: */
{ -1, -1, 17 }, /* 32: (5, 1) 12 bits */
{ -1, -1, 15 }, /* 33: (5,-1) 12 bits */
{ 35, 36, -1 }, /* 34: */
{ -1, -1, 19 }, /* 35: (6, 0) 12 bits */
{ -1, -1, 20 }, /* 36: (6, 1) 12 bits */
{ 38, 41, -1 }, /* 37: */
{ 39, 40, -1 }, /* 38: */
{ -1, -1, 18 }, /* 39: (6,-1) 12 bits */
{ -1, -1, 22 }, /* 40: (7, 0) 12 bits */
{ 42, 43, -1 }, /* 41: */
{ -1, -1, 23 }, /* 42: (7, 1) 12 bits */
{ -1, -1, 21 }, /* 43: (7,-1) 12 bits */
{ -1, -1, 5 }, /* 44: (1, 1) 6 bits */
{ -1, -1, 2 }, /* 45: (0, 1) 4 bits */
{ -1, -1, 7 }, /* 46: (2, 0) 3 bits */
};
Encoding Table
static bliss_huffman_code_tuple_t tuples[] = {
{ 24, 5 }, /* 0: (0,-1) 11000 */
{ 0, 1 }, /* 1: (0, 0) 0 */
{ 13, 4 }, /* 2: (0, 1) 1101 */
{ 100, 7 }, /* 3: (1,-1) 1100100 */
{ 2, 2 }, /* 4: (1, 0) 10 */
{ 51, 6 }, /* 5: (1, 1) 110011 */
{ 3249, 12 }, /* 6: (2,-1) 110010110001 */
{ 7, 3 }, /* 7: (2, 0) 111 */
{ 3248, 12 }, /* 8: (2, 1) 110010110000 */
{ 3251, 12 }, /* 9: (3,-1) 110010110011 */
{ 202, 8 }, /* 10: (3, 0) 11001010 */
{ 3250, 12 }, /* 11: (3, 1) 110010110010 */
{ 3254, 12 }, /* 12: (4,-1) 110010110110 */
{ 3252, 12 }, /* 13: (4, 0) 110010110100 */
{ 3253, 12 }, /* 14: (4, 1) 110010110101 */
{ 3257, 12 }, /* 15: (5,-1) 110010111001 */
{ 3255, 12 }, /* 16: (5, 0) 110010110111 */
{ 3256, 12 }, /* 17: (5, 1) 110010111000 */
{ 3260, 12 }, /* 18: (6,-1) 110010111100 */
{ 3258, 12 }, /* 19: (6, 0) 110010111010 */
{ 3259, 12 }, /* 20: (6, 1) 110010111011 */
{ 3263, 12 }, /* 21: (7,-1) 110010111111 */
{ 3261, 12 }, /* 22: (7, 0) 110010111101 */
{ 3262, 12 }, /* 23: (7, 1) 110010111110 */
};
/* code_length = 1.3189 bits/tuple (676 bits) */
Parameter Set
bliss_huffman_code_t bliss_huffman_code_1 = {
.n_z1 = 8,
.n_z2 = 2,
.tuples = tuples,
.nodes = nodes
};
BLISS-III Signature Encoding¶
Design Parameters
/* * Design: sigma = 250 * * i p_z1[i] * 0 0.6941647250930416 0 .. 256 * 1 0.2652752755116807 256 .. 512 * 2 0.0384337021454129 512 .. 768 * 3 0.0020842622589255 768 .. 1024 * 4 0.0000417294572050 1024 .. 1280 * 5 0.0000003047309681 1280 .. 1536 * 6 0.0000000008027661 1536 .. 1760 * * k p_z2[k] dx = 512 * -3 0.0000001543959154 -1791.5 ..-1279.5 * -2 0.0010701394583782 -1279.5 .. -767.5 * -1 0.1523201563502276 -767.5 .. -255.5 * 0 0.6932190995909575 -255.5 .. 255.5 * 1 0.1523201563502276 255.5 .. 767.5 * 2 0.0010701394583782 767.5 .. 1279.5 * 3 0.0000001543959154 1279.5 .. 1791.5 * * (i, k) p * (0,-3) 0.0000001071761982 * (0,-2) 0.0007428530629363 * (0,-1) 0.1057352794589848 * (0, 0) 0.4812082456968029 * (0, 1) 0.1057352794589848 * (0, 2) 0.0007428530629363 * (0, 3) 0.0000001071761982 * * (1,-3) 0.0000000409574190 * (1,-2) 0.0002838815396572 * (1,-1) 0.0404067714417889 * (1, 0) 0.1838938876339505 * (1, 1) 0.0404067714417889 * (1, 2) 0.0002838815396572 * (1, 3) 0.0000000409574190 * * (2,-3) 0.0000000059340066 * (2,-2) 0.0000411294211974 * (2,-1) 0.0058542275199074 * (2, 0) 0.0266429763951902 * (2, 1) 0.0058542275199074 * (2, 2) 0.0000411294211974 * (2, 3) 0.0000000059340066 * * (3,-3) 0.0000000003218016 * (3,-2) 0.0000022304512849 * (3,-1) 0.0003174751531544 * (3, 0) 0.0014448504064437 * (3, 1) 0.0003174751531544 * (3, 2) 0.0000022304512849 * (3, 3) 0.0000000003218016 * * (4,-3) 0.0000000000064429 * (4,-2) 0.0000000446563387 * (4,-1) 0.0000063562374459 * (4, 0) 0.0000289276567501 * (4, 1) 0.0000063562374459 * (4, 2) 0.0000000446563387 * (4, 3) 0.0000000000064429 * * (5,-3) 0.0000000000000470 * (5,-2) 0.0000000003261046 * (5,-1) 0.0000000464166687 * (5, 0) 0.0000002112453273 * (5, 1) 0.0000000464166687 * (5, 2) 0.0000000003261046 * (5, 3) 0.0000000000000470 * * (6,-3) 0.0000000000000001 * (6,-2) 0.0000000000008591 * (6,-1) 0.0000000001222775 * (6, 0) 0.0000000005564928 * (6, 1) 0.0000000001222775 * (6, 2) 0.0000000000008591 * (6, 3) 0.0000000000000001 * * p_sum 0.9999999999999999 * * entropy = 2.2879 bits/tuple (1171 bits) */
Decoding Tree
#include "bliss_huffman_code.h"
static bliss_huffman_code_node_t nodes[] = {
{ 1, 96, -1 }, /* 0: */
{ 2, 93, -1 }, /* 1: */
{ 3, 4, -1 }, /* 2: */
{ -1, -1, 10 }, /* 3: (1, 0) 3 bits */
{ 5, 8, -1 }, /* 4: */
{ 6, 7, -1 }, /* 5: */
{ -1, -1, 11 }, /* 6: (1, 1) 5 bits */
{ -1, -1, 9 }, /* 7: (1,-1) 5 bits */
{ 9, 10, -1 }, /* 8: */
{ -1, -1, 17 }, /* 9: (2, 0) 5 bits */
{ 11, 92, -1 }, /* 10: */
{ 12, 13, -1 }, /* 11: */
{ -1, -1, 16 }, /* 12: (2,-1) 7 bits */
{ 14, 89, -1 }, /* 13: */
{ 15, 16, -1 }, /* 14: */
{ -1, -1, 24 }, /* 15: (3, 0) 9 bits */
{ 17, 86, -1 }, /* 16: */
{ 18, 85, -1 }, /* 17: */
{ 19, 20, -1 }, /* 18: */
{ -1, -1, 8 }, /* 19: (1,-2) 12 bits */
{ 21, 84, -1 }, /* 20: */
{ 22, 53, -1 }, /* 21: */
{ 23, 38, -1 }, /* 22: */
{ 24, 31, -1 }, /* 23: */
{ 25, 28, -1 }, /* 24: */
{ 26, 27, -1 }, /* 25: */
{ -1, -1, 15 }, /* 26: (2,-2) 18 bits */
{ -1, -1, 31 }, /* 27: (4, 0) 18 bits */
{ 29, 30, -1 }, /* 28: */
{ -1, -1, 32 }, /* 29: (4, 1) 18 bits */
{ -1, -1, 30 }, /* 30: (4,-1) 18 bits */
{ 32, 35, -1 }, /* 31: */
{ 33, 34, -1 }, /* 32: */
{ -1, -1, 26 }, /* 33: (3, 2) 18 bits */
{ -1, -1, 22 }, /* 34: (3,-2) 18 bits */
{ 36, 37, -1 }, /* 35: */
{ -1, -1, 38 }, /* 36: (5, 0) 18 bits */
{ -1, -1, 6 }, /* 37: (0, 3) 18 bits */
{ 39, 46, -1 }, /* 38: */
{ 40, 43, -1 }, /* 39: */
{ 41, 42, -1 }, /* 40: */
{ -1, -1, 0 }, /* 41: (0,-3) 18 bits */
{ -1, -1, 39 }, /* 42: (5, 1) 18 bits */
{ 44, 45, -1 }, /* 43: */
{ -1, -1, 37 }, /* 44: (5,-1) 18 bits */
{ -1, -1, 33 }, /* 45: (4, 2) 18 bits */
{ 47, 50, -1 }, /* 46: */
{ 48, 49, -1 }, /* 47: */
{ -1, -1, 29 }, /* 48: (4,-2) 18 bits */
{ -1, -1, 13 }, /* 49: (1, 3) 18 bits */
{ 51, 52, -1 }, /* 50: */
{ -1, -1, 7 }, /* 51: (1,-3) 18 bits */
{ -1, -1, 20 }, /* 52: (2, 3) 18 bits */
{ 54, 69, -1 }, /* 53: */
{ 55, 62, -1 }, /* 54: */
{ 56, 59, -1 }, /* 55: */
{ 57, 58, -1 }, /* 56: */
{ -1, -1, 14 }, /* 57: (2,-3) 18 bits */
{ -1, -1, 45 }, /* 58: (6, 0) 18 bits */
{ 60, 61, -1 }, /* 59: */
{ -1, -1, 40 }, /* 60: (5, 2) 18 bits */
{ -1, -1, 36 }, /* 61: (5,-2) 18 bits */
{ 63, 66, -1 }, /* 62: */
{ 64, 65, -1 }, /* 63: */
{ -1, -1, 27 }, /* 64: (3, 3) 18 bits */
{ -1, -1, 21 }, /* 65: (3,-3) 18 bits */
{ 67, 68, -1 }, /* 66: */
{ -1, -1, 46 }, /* 67: (6, 1) 18 bits */
{ -1, -1, 44 }, /* 68: (6,-1) 18 bits */
{ 70, 77, -1 }, /* 69: */
{ 71, 74, -1 }, /* 70: */
{ 72, 73, -1 }, /* 71: */
{ -1, -1, 34 }, /* 72: (4, 3) 18 bits */
{ -1, -1, 28 }, /* 73: (4,-3) 18 bits */
{ 75, 76, -1 }, /* 74: */
{ -1, -1, 47 }, /* 75: (6, 2) 18 bits */
{ -1, -1, 43 }, /* 76: (6,-2) 18 bits */
{ 78, 81, -1 }, /* 77: */
{ 79, 80, -1 }, /* 78: */
{ -1, -1, 41 }, /* 79: (5, 3) 18 bits */
{ -1, -1, 35 }, /* 80: (5,-3) 18 bits */
{ 82, 83, -1 }, /* 81: */
{ -1, -1, 48 }, /* 82: (6, 3) 18 bits */
{ -1, -1, 42 }, /* 83: (6,-3) 18 bits */
{ -1, -1, 19 }, /* 84: (2, 2) 13 bits */
{ -1, -1, 25 }, /* 85: (3, 1) 11 bits */
{ 87, 88, -1 }, /* 86: */
{ -1, -1, 23 }, /* 87: (3,-1) 11 bits */
{ -1, -1, 12 }, /* 88: (1, 2) 11 bits */
{ 90, 91, -1 }, /* 89: */
{ -1, -1, 5 }, /* 90: (0, 2) 9 bits */
{ -1, -1, 1 }, /* 91: (0,-2) 9 bits */
{ -1, -1, 18 }, /* 92: (2, 1) 6 bits */
{ 94, 95, -1 }, /* 93: */
{ -1, -1, 4 }, /* 94: (0, 1) 3 bits */
{ -1, -1, 2 }, /* 95: (0,-1) 3 bits */
{ -1, -1, 3 }, /* 96: (0, 0) 1 bit */
};
Encoding Table
static bliss_huffman_code_tuple_t tuples[] = {
{ 59976, 18 }, /* 0: (0,-3) 001110101001001000 */
{ 119, 9 }, /* 1: (0,-2) 001110111 */
{ 3, 3 }, /* 2: (0,-1) 011 */
{ 1, 1 }, /* 3: (0, 0) 1 */
{ 2, 3 }, /* 4: (0, 1) 010 */
{ 118, 9 }, /* 5: (0, 2) 001110110 */
{ 59975, 18 }, /* 6: (0, 3) 001110101001000111 */
{ 59982, 18 }, /* 7: (1,-3) 001110101001001110 */
{ 936, 12 }, /* 8: (1,-2) 001110101000 */
{ 5, 5 }, /* 9: (1,-1) 00101 */
{ 0, 3 }, /* 10: (1, 0) 000 */
{ 4, 5 }, /* 11: (1, 1) 00100 */
{ 471, 11 }, /* 12: (1, 2) 00111010111 */
{ 59981, 18 }, /* 13: (1, 3) 001110101001001101 */
{ 59984, 18 }, /* 14: (2,-3) 001110101001010000 */
{ 59968, 18 }, /* 15: (2,-2) 001110101001000000 */
{ 28, 7 }, /* 16: (2,-1) 0011100 */
{ 6, 5 }, /* 17: (2, 0) 00110 */
{ 15, 6 }, /* 18: (2, 1) 001111 */
{ 1875, 13 }, /* 19: (2, 2) 0011101010011 */
{ 59983, 18 }, /* 20: (2, 3) 001110101001001111 */
{ 59989, 18 }, /* 21: (3,-3) 001110101001010101 */
{ 59973, 18 }, /* 22: (3,-2) 001110101001000101 */
{ 470, 11 }, /* 23: (3,-1) 00111010110 */
{ 116, 9 }, /* 24: (3, 0) 001110100 */
{ 469, 11 }, /* 25: (3, 1) 00111010101 */
{ 59972, 18 }, /* 26: (3, 2) 001110101001000100 */
{ 59988, 18 }, /* 27: (3, 3) 001110101001010100 */
{ 59993, 18 }, /* 28: (4,-3) 001110101001011001 */
{ 59980, 18 }, /* 29: (4,-2) 001110101001001100 */
{ 59971, 18 }, /* 30: (4,-1) 001110101001000011 */
{ 59969, 18 }, /* 31: (4, 0) 001110101001000001 */
{ 59970, 18 }, /* 32: (4, 1) 001110101001000010 */
{ 59979, 18 }, /* 33: (4, 2) 001110101001001011 */
{ 59992, 18 }, /* 34: (4, 3) 001110101001011000 */
{ 59997, 18 }, /* 35: (5,-3) 001110101001011101 */
{ 59987, 18 }, /* 36: (5,-2) 001110101001010011 */
{ 59978, 18 }, /* 37: (5,-1) 001110101001001010 */
{ 59974, 18 }, /* 38: (5, 0) 001110101001000110 */
{ 59977, 18 }, /* 39: (5, 1) 001110101001001001 */
{ 59986, 18 }, /* 40: (5, 2) 001110101001010010 */
{ 59996, 18 }, /* 41: (5, 3) 001110101001011100 */
{ 59999, 18 }, /* 42: (6,-3) 001110101001011111 */
{ 59995, 18 }, /* 43: (6,-2) 001110101001011011 */
{ 59991, 18 }, /* 44: (6,-1) 001110101001010111 */
{ 59985, 18 }, /* 45: (6, 0) 001110101001010001 */
{ 59990, 18 }, /* 46: (6, 1) 001110101001010110 */
{ 59994, 18 }, /* 47: (6, 2) 001110101001011010 */
{ 59998, 18 }, /* 48: (6, 3) 001110101001011110 */
};
/* code_length = 2.3227 bits/tuple (1190 bits) */
Parameter Set
bliss_huffman_code_t bliss_huffman_code_3 = {
.n_z1 = 7,
.n_z2 = 4,
.tuples = tuples,
.nodes = nodes
};
BLISS-IV Signature Encoding¶
Design Parameters
Decoding Tree
Encoding Table
Parameter Set