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

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 $S_1, S_2, \ldots, S_n$ can be transmitted, each taking a specific amount of time $t_i$. For instance, in telegraphy:

1. A dot (one unit of time and one unit open).
2. A dash (three units of close and one unit open).
3. A letter space (three units open).
4. 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 $C$ of a discrete channel is defined as:

Where $N(T)$ is the number of allowed signals of duration $T$.

Explanation

• $N(T)$: Number of allowed sequences of length $T$.
• $\log N(T)$: Logarithm of the number of sequences, which relates to the amount of information.
• $\frac{\log N(T)}{T}$: Average information per unit time.

In simpler terms, $C$ measures how much information per time unit the channel can transmit when $T$ 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 $5n$ bits per second if the system transmits $n$ symbols per second.

General Case

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

Mathematical Details

Given symbols $S_1, S_2, \ldots, S_n$ with durations $t_1, t_2, \ldots, t_n$:

This recurrence relation shows $N(t)$ as a sum of sequences ending in each symbol $S_i$.

For large $t$, $N(t)$ follows a characteristic equation related to the largest real solution $X_0$:

This equation helps in finding the asymptotic behavior of $N(t)$ and thus the channel capacity $C$.

Summary

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

Understanding $N(t)$ and the Characteristic Equation

Why is $N(t)$ the Sum?

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

1. Allowed Sequences:
• You have a set of symbols $S_1, S_2, \ldots, S_n$ with corresponding durations $t_1, t_2, \ldots, t_n$.
• Each sequence of total duration $t$ can end in any of these symbols.
2. Recursive Nature:
• Suppose you know the number of allowed sequences for all durations less than $t$.
• To find $N(t)$, consider the sequence could end with $S_i$, which has a duration $t_i$.
• The remaining duration before $S_i$ must then be $t - t_i$.
• Therefore, the number of sequences of duration $t$ that end in $S_i$ is $N(t - t_i)$.
3. Summing Over All Possible Endings:
• The total number of sequences of duration $t$ 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:

1. Assume a Solution Form:
• Assume $N(t) = X^t$ is a solution to the recurrence relation. This is a common technique to solve linear recurrence relations.
• Substitute $N(t) = X^t$ into the recurrence relation:
$$$$
2. Simplify the Equation:
• Divide through by $X^t$:
$$$$
3. Characteristic Equation:
• The equation $1 = X^{-t_1} + X^{-t_2} + \ldots + X^{-t_n}$ is known as the characteristic equation.
• Solving this equation for $X$ gives the characteristic roots, which help in understanding the behavior of $N(t)$.

Finding $N(t)$ Asymptotically

1. Largest Real Solution:
• The largest real solution $X_0$ to the characteristic equation determines the dominant term in the growth of $N(t)$.
• As $t$ becomes large, $N(t)$ behaves asymptotically like $X_0^t$.
2. Channel Capacity:
• Since $\log N(t) \approx t \log X_0$ for large $t$, the channel capacity $C$ is: $C = \lim_{T \to \infty} \frac{\log N(T)}{T} = \log X_0$

Summary

• Recurrence Relation: $N(t) = N(t - t_1) + N(t - t_2) + \ldots + N(t - t_n)$ because each sequence can end in any of the symbols $S_i$.
• Characteristic Equation: Found by assuming a solution form $N(t) = X^t$ and simplifying to $1 = X^{-t_1} + X^{-t_2} + \ldots + X^{-t_n}$.
• Capacity: The capacity $C$ is related to the largest real solution $X_0$ of the characteristic equation, where $C = \log X_0$.

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 $n$-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:

1. Mathematics:
• Combinatorics: To count objects and solve counting problems.
• Number Theory: For sequences like Fibonacci numbers.
2. Computer Science:
• Algorithms: To analyze the time complexity of recursive algorithms.
• Data Structures: To determine properties of structures like trees and heaps.
3. 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 $a_n = r^n$ 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:

1. Assume a Solution:
• $a_n = r^n$
2. Substitute and Form the Characteristic Equation:
• Substitute $a_n = r^n$ into the recurrence relation: $r^n = c_1 r^{n-1} + c_2 r^{n-2} + \ldots + c_k r^{n-k}$
• Divide by $r^{n-k}$ to get: $r^k = c_1 r^{k-1} + c_2 r^{k-2} + \ldots + c_k$
• This is the characteristic equation.
3. Solve the Characteristic Equation:
• Find the roots $r_1, r_2, \ldots, r_k$.
4. Form the General Solution:
• The general solution is a linear combination of the roots:
$$$$
• Use initial conditions to solve for the constants $A_1, A_2, \ldots, A_k$.

Example: Fibonacci Sequence

The Fibonacci sequence is defined by:

1. Characteristic Equation:

1. $r^2 - r - 1 = 0$
2. Solve for Roots: $r = \frac{1 \pm \sqrt{5}}{2}$ Let $\alpha = \frac{1 + \sqrt{5}}{2}$ and $\beta = \frac{1 - \sqrt{5}}{2}$.
3. General Solution: $F_n = A \alpha^n + B \beta^n$ Use initial conditions to find $A$ and $B$: $F_0 = 0 \implies A + B = 0 \implies B = -A$ $F_1 = 1 \implies A \alpha + B \beta = 1 \implies A (\alpha - \beta) = 1 \implies A = \frac{1}{\alpha - \beta} = \frac{1}{\sqrt{5}}$ 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.