fibonacci coding
先日ある方からお話を少し聞いたので考察目的で少々。
fibonacci codingとは、フィボナッチ数列を用いた符号化方式の一つです。
フィボナッチ数列は隣あった２数を足した数を次の数とした数列のことで、1,1,2,3,5,8,13…となっています。
このフィボナッチ数列の性質として、すべての自然数は隣合わない数列の数を足し合わせることで表現できるというものがあります。(負の数は符号が一つずつ逆転するといった複雑な形になっているので今回の話では取り扱いません)
このフィボナッチ数列を利用して、数値の符号化をすることができます。
まず、フィボナッチ数列を x[ i ]（i >= 0）と表すことにします。
これを用いて、なるべく少ない加算で自然数を順に表していくと、
1 → x[ 1 ]
2 → x[ 2 ]
3 → x[ 3 ]
4 → x[ 1 ] + x[ 3 ]
5 → x[ 4 ]
6 → x[ 1 ] + x[ 4 ]
7 → x[ 2 ] + x[ 4 ]
8 → x[ 5 ]
9 → x[ 1 ] + x[ 5 ]
10 → x[ 2 ] + x[ 5 ]
といった具合になります。
そして、配列の使われている要素を1,使われていない要素を0として表すと、
1 → 00001
2 → 00010
3 → 00100
4 → 00101
5 → 01000
6 → 01001
7 → 01010
8 → 10000
9 → 10001
10 → 10010
このように符号として表すことができます。
これをfibonacci codingと呼びます。
fibonacci codingの特徴として、1は絶対に２回続けて登場しないというのがあります。
これはとても珍しい特徴で、もし11という部分があれば誤りが発生していることがわかります。
圧縮などにはあまり効果は見られないですが、誤り検知に優れているという特性を用いて活用できるところがあると思います。(これ以上は先行研究を詳しく知らないため掘り下げないでおきます)
ちなみにこの話をしていただいた方の論文内容であるネイピアの計算盤を用いればfibonacci coding同士の掛け算ができるそうで、論文の方今度詳しく読まさせていただきます。
fibonacci codingとは、フィボナッチ数列を用いた符号化方式の一つです。
フィボナッチ数列は隣あった２数を足した数を次の数とした数列のことで、1,1,2,3,5,8,13…となっています。
このフィボナッチ数列の性質として、すべての自然数は隣合わない数列の数を足し合わせることで表現できるというものがあります。(負の数は符号が一つずつ逆転するといった複雑な形になっているので今回の話では取り扱いません)
このフィボナッチ数列を利用して、数値の符号化をすることができます。
まず、フィボナッチ数列を x[ i ]（i >= 0）と表すことにします。
これを用いて、なるべく少ない加算で自然数を順に表していくと、
1 → x[ 1 ]
2 → x[ 2 ]
3 → x[ 3 ]
4 → x[ 1 ] + x[ 3 ]
5 → x[ 4 ]
6 → x[ 1 ] + x[ 4 ]
7 → x[ 2 ] + x[ 4 ]
8 → x[ 5 ]
9 → x[ 1 ] + x[ 5 ]
10 → x[ 2 ] + x[ 5 ]
といった具合になります。
そして、配列の使われている要素を1,使われていない要素を0として表すと、
1 → 00001
2 → 00010
3 → 00100
4 → 00101
5 → 01000
6 → 01001
7 → 01010
8 → 10000
9 → 10001
10 → 10010
このように符号として表すことができます。
これをfibonacci codingと呼びます。
fibonacci codingの特徴として、1は絶対に２回続けて登場しないというのがあります。
これはとても珍しい特徴で、もし11という部分があれば誤りが発生していることがわかります。
圧縮などにはあまり効果は見られないですが、誤り検知に優れているという特性を用いて活用できるところがあると思います。(これ以上は先行研究を詳しく知らないため掘り下げないでおきます)
ちなみにこの話をしていただいた方の論文内容であるネイピアの計算盤を用いればfibonacci coding同士の掛け算ができるそうで、論文の方今度詳しく読まさせていただきます。
