Skip to content

rust-common/tbe

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TBE

Truncated Binary Encoding

https://en.wikipedia.org/wiki/Truncated_binary_encoding

k = floor_log2(n);
u = 2 * exp2(k) - n

Writing

if x < u write k least significant bits of x else add u to x and write k most significant bits of x and then write a least significant bit of x.

Reading

  1. read k bits as x.
  2. if u <= x then read an additional bit and add it to x as a least significant bit and substract u.

Examples (MSB first)

n = 2

k = 1;
u = 4 - 2 = 2;
BE TBE
0 0
1 1
n u

n = 3

k = 2;
u = 1
BE TBE(MSB) TBE(LSB)
00 0X 0X
01 10 10 u
10 11 11

n = 4

k = 2
u = 8 - 4 = 4
BE TBE
00 00
01 01
10 10
11 11
n u

n = 5

k = 2;
u = 3;
BE TBE
000 00
001 01
010 10
011 110 u
100 111

n = 6

k = 2;
u = 2;
BE TBE
000 00
001 01
010 100
011 101
100 110
101 111

n = 7

BE TBE
000 00
001 010
010 011
011 100
100 101
101 110
110 111

n = 10

k = 3;
u = 6;
BE TBE(MSB) TBE(LSB)
0000 000X 000X
0001 001X 100X
0010 010X 010X
0011 011X 110X
0100 100X 001X
0101 101X 101X
0110 1100 0110
0111 1101 0111
1000 1110 1110
1001 1111 1111

Releases

No releases published

Packages

No packages published

Languages