[Huffman codes' connection with Fibonacci and Lucas numbers] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Huffman codes' connection with Fibonacci and Lucas numbers

(Click here to view the original thread with full colors/images)


Posted by: Alex Vinokur

Does NKS contain mention of Huffman codes' connection with Fibonacci and Lucas numbers?

Here is a brief description of such a connection:
http://mathforum.org/discuss/sci.math/t/632220
http://groups.google.com/groups?sel...40uni-berlin.de


Posted by: Jason Cawley

Not in that level of detail. But there is mention of the connection between Fibonacci numbers (and other sequences) and trees - in the section on substitution systems, (see e.g. 83 especially plot "c" and the accompanying notes, especially 891). There is also implimentation code of Huffman coding on page 1071, which might be helpful for those exploring the relationship.


Posted by: Alex Vinokur

Fibonacci connection between non-decreasing sequences of positive integers producing maximum height Huffman trees and the Wythoff array has been proved.

The paper can be seen at
* http://arxiv.org/abs/cs.DM/0410013

The abstract can be seen at
* http://groups.google.com/groups?sel...40uni-berlin.de
* http://mathforum.org/epigone/sci.ma.../pherdkralglend


Posted by: Alex Vinokur

Fibonacci connection between Huffman codes and Wythoff array:
The brief description with examples can be seen at
* http://groups.google.com/groups?sel...40uni-berlin.de
* http://mathforum.org/discuss/sci.math/m/641586/642072


Posted by: Jon Awbrey

Alex,

This sounds interesting, but the Math Forum notes
were a little hard to follow. Could you provide
a more self-contained exposition from scratch
for someone who doesn't already know all the
definitions?

Thanks In Prospect,

Jon Awbrey


Posted by: Alex Vinokur

Originally posted by Jon Awbrey
Alex,

This sounds interesting, but the Math Forum notes
were a little hard to follow. Could you provide
a more self-contained exposition from scratch
for someone who doesn't already know all the
definitions?

Thanks In Prospect,

Jon Awbrey


Jon, thank you for your feedback.

I should think how to do that.

Is it worth describing the problem and solution in informal way, with pictures? Without formal definitions and formulations?

Thanks,
Alex


Posted by: Jon Awbrey

Alex,

Yes^2, I for 1 would appreciate that.
For my part, I had quite a bit of
number theory once upon a time,
but may be a little rusty on
the more arcane definitions,
and how they relate to CA's.

Best Wishes,

Jon Awbrey


Posted by: Alex Vinokur

Jon,

I will try to do that.
Of course, it will take me some time.

Regards,
Alex




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings