Exploring the Connection: Fibonacci Series and Shannon's Discrete, Noiseless Channel Capacity

This section from the paper discusses the concept of a discrete noiseless channel.

Overview

A discrete noiseless channel is a system for transmitting information without errors. This means that the transmitted symbols are received exactly as sent. Two historical examples are the teletype and telegraphy.

Symbols and Transmission

In such a channel, symbols can be transmitted, each taking a specific amount of time . For instance, in telegraphy:

A dot (one unit of time and one unit open).
A dash (three units of close and one unit open).
A letter space (three units open).
A word space (six units open).

The capacity of the channel, which is the maximum rate at which information can be transmitted, is the main focus.

Channel Capacity Definition

The capacity of a discrete channel is defined as:

Where is the number of allowed signals of duration .

Explanation

: Number of allowed sequences of length .
: Logarithm of the number of sequences, which relates to the amount of information.
: Average information per unit time.

In simpler terms, measures how much information per time unit the channel can transmit when becomes very large.

Special Case: Teletype Channel

For the teletype example, if all symbols have the same duration and there are 32 symbols, each symbol represents five bits. Thus, the capacity would be bits per second if the system transmits symbols per second.

General Case

For different lengths of symbols and constraints on durations, the capacity is given by the below.

Mathematical Details

Given symbols with durations :

This recurrence relation shows as a sum of sequences ending in each symbol .

For large , follows a characteristic equation related to the largest real solution :

This equation helps in finding the asymptotic behavior of and thus the channel capacity .

Summary

Channel Capacity measures the information rate of a noiseless channel.
For teletype, is straightforward when all symbols are equal duration.
General case involves solving a recurrence relation to find .
Characteristic Equation is used to find the asymptotic behavior of .

Understanding and the Characteristic Equation

Why is the Sum?

represents the number of allowed sequences of duration . Let's break down why can be expressed as a sum:

Allowed Sequences:

You have a set of symbols with corresponding durations .
Each sequence of total duration can end in any of these symbols.

Recursive Nature:

Suppose you know the number of allowed sequences for all durations less than .
To find , consider the sequence could end with , which has a duration .
The remaining duration before must then be .
Therefore, the number of sequences of duration that end in is .

Summing Over All Possible Endings:

The total number of sequences of duration is the sum of all sequences ending in each possible symbol.
This gives us the recurrence relation:

From Recurrence to Characteristic Equation

To solve the recurrence relation, we use generating functions or characteristic equations. Here’s a step-by-step outline of how we get to the characteristic equation:

Assume a Solution Form:

Assume is a solution to the recurrence relation. This is a common technique to solve linear recurrence relations.
Substitute into the recurrence relation:

Simplify the Equation:

Divide through by :

Characteristic Equation:

The equation is known as the characteristic equation.
Solving this equation for gives the characteristic roots, which help in understanding the behavior of .

Finding Asymptotically

Largest Real Solution:

The largest real solution to the characteristic equation determines the dominant term in the growth of .
As becomes large, behaves asymptotically like .

Channel Capacity:

Since for large , the channel capacity is:

Summary

Recurrence Relation: because each sequence can end in any of the symbols .
Characteristic Equation: Found by assuming a solution form and simplifying to .
Capacity: The capacity is related to the largest real solution of the characteristic equation, where .

This framework allows us to transition from a combinatorial counting problem to a manageable algebraic equation that provides insights into the channel's capacity.

Recurrence Equation Definition

What is a Recurrence Equation?

A recurrence equation (or recurrence relation) is an equation that recursively defines a sequence: each term of the sequence is defined as a function of the preceding terms. In other words, it expresses the -th term of the sequence as a function of one or more of its previous terms.

Fields of Study

Recurrence equations are primarily used in the following fields:

Mathematics:

Combinatorics: To count objects and solve counting problems.
Number Theory: For sequences like Fibonacci numbers.

Computer Science:

Algorithms: To analyze the time complexity of recursive algorithms.
Data Structures: To determine properties of structures like trees and heaps.

Engineering:

Signal Processing: For digital filters and system responses.

Solving Recurrence Equations

There are several methods to solve recurrence equations, depending on their form and complexity:

1. Iterative Method

Compute the first few terms manually and look for a pattern.
Useful for simple recurrences with obvious patterns.

2. Substitution Method

Guess the form of the solution and use mathematical induction to prove it.
Example: For linear homogeneous recurrences.

3. Characteristic Equation Method

Used for linear recurrences with constant coefficients.
Assume solutions of the form and derive the characteristic polynomial.
Solve the characteristic equation to find the roots.

Example: Linear Homogeneous Recurrence Relation

Consider the recurrence relation:

Steps to solve using the characteristic equation method:

Assume a Solution:

Substitute and Form the Characteristic Equation:

Substitute into the recurrence relation:
Divide by to get:
This is the characteristic equation.

Solve the Characteristic Equation:

Find the roots .

Form the General Solution:

The general solution is a linear combination of the roots:

Use initial conditions to solve for the constants .

Example: Fibonacci Sequence

The Fibonacci sequence is defined by:

Characteristic Equation:

Solve for Roots: Let and .
General Solution: Use initial conditions to find and : Hence,

Python code

import math

# Recursive Fibonacci function
def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# Direct Fibonacci function using the closed-form expression (Binet's formula)
def fibonacci_direct(n):
    sqrt_5 = math.sqrt(5)
    alpha = (1 + sqrt_5) / 2
    beta = (1 - sqrt_5) / 2
    return int((alpha**n - beta**n) / sqrt_5)

# Compare results
n_terms = 10  # Number of terms to compare
recursive_results = [fibonacci_recursive(n) for n in range(n_terms)]
direct_results = [fibonacci_direct(n) for n in range(n_terms)]

# Print results
print("n\tRecursive\tDirect")
for n in range(n_terms):
    print(f"{n}\t\t{recursive_results[n]}\t\t\t{direct_results[n]}")

# Check if both methods yield the same results
for n in range(n_terms):
    assert recursive_results[n] == direct_results[n], f"Mismatch at term {n}"
print("Both methods yield the same results.")

n	Recursive	Direct
0		0				0
1		1				1
2		1				1
3		2				2
4		3				3
5		5				5
6		8				8
7		13			13
8		21			21
9		34			34
Both methods yield the same results.

Summary

Recurrence Equation: Defines a sequence recursively.
Fields: Mathematics, Computer Science, Engineering.
Solving Methods: Iterative, Substitution, Characteristic Equation.
Example: Fibonacci sequence solution using the characteristic equation method.
Comparison between the well known Fibonacci recursion and it’s direct solution.