[MS] While rereading ''' Data Compression''' [http://www.ics.uci.edu/~dan/pubs/DataCompression.html], I stumbled on Fibonacci universal codes (see Section 3.3 [http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html#Sec_3.3]).

Here it is in Tcl:

 #
 # A memoizing generator for the Fibonacci numbers.  
 #
 
 variable fiboList [list 1 1]
 proc fibo n {
     variable fiboList
     set len [llength $fiboList]
     if {$len > $n} {
 	return [lindex $fiboList $n]
     } 
     set res [expr {[fibo [expr {$n-2}]] + [fibo [expr {$n-1}]]}]
     lappend fiboList $res
     return $res
 }
 
 #
 # Computing the Fibonacci encoding of a number - see 
 # http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html#Sec_3
 # (memoizing)
 
 variable fiboEncs
 proc fiboEncode n {
     if {$n < 1} {
 	error "fiboEncode works on positive numbers"
     }
     variable fiboEncs
     if {[info exists fiboEncs($n)]} {
 	return $fiboEncs($n)
     }
     upvar 0 fiboEncs($n) res
     set res 1
 
     # Find the first fibonacci number $f > $n
     set f 1
     for {set k 1} {$f <= $n} {} {
 	set f [fibo [incr k]]
     }
 
     while {[incr k -1]} {
 	set f [fibo $k]
 	if {$f <= $n} {
 	    set res 1$res
 	    incr n -$f
 	} else {
 	    set res 0$res
 	}
     }
     return $res
 }
 
 proc fiboDecode str {
     set coeffs [split $str {}]
     if {([lindex $coeffs end] != 1) 
 	|| ([lindex $coeffs end-1] != 1)} {
 	error "Number badly encoded"
     }
     set n 0
     set k 0
     foreach c [lrange $coeffs 0 end-1] {
 	incr k
 	if {$c} {
 	    incr n [fibo $k]
 	}
     }
     set n
 }