2025-03-08
If we can model the world using finite state machines and these machines, in practice, are deterministic, must we import a belief in determinism at a deeper level in our analysis? This is a difficult question 1) due to the limited extent of our knowledge and 2) due to what one might want to believe about freedom of will. Both of these challenges will play a role in discussion. I will base my discussion of the topic on what is described by Paul Lewis as a "computational argument" for a pragmatic dualism that treats emergent structures like consciousness as something that cannot be adequately described by its individual parts (Lewis 2017). I will show that even if we presume that the world is deterministic, various factors will necessarily limit the extent to which we can predict outcomes in complex systems. In accord with Hayek, what follows is not an argument for determinism but, rather, an argument for treating the world as deterministic in order to make modeling possible while simultaneously recognizing the epistemic limitations that limit the generalizability of inferences drawn from the model.
For those who fear that determinism equates to control, one might alleviate their disease by recognizing that if the world is deterministic, details that determine outcomes are not sufficiently known such that one could have perfect foresight. Neither are we able to compute, ahead of time, interactions that generate unexpected behavior. Complex interaction within even just the modeled aspects of the socio-economic systems limits the extent of prediction. This is why we must observe many iterations of a model to understand it. Or else just the description provided by the script would be sufficient for understanding the system.
Reality lacks a script that humans can access directly. Our world, physical, biological, and social, includes not only a vast reportoire of behaviors and their interactions, but also probabilities that appear to govern transitions between states within a system. And supposing that agents in the system attempt to intelligently navigate the environment, understanding of the environment must somehow integrate the agent's own intelligence. Finally, there is error in interpretation of data as well as error in the data itself that the agents use to interpret the environment.
Hayek recognized the challenges that complexity generated for predicting deterministic systems. Hayek appears not to have been bothered by determinism in modeling. In "The Theory of Complex Phenomena", Hayek observes that if the world operated in such a manner:
[t]he chief fact would continue to be, in spite of our knowledge of the principle on which the human mind works, that we should not be able to state the full set of particular facts which brought it about that the individual did a particular thing at a particular time. The individual personality would remain for us as much a unique and unaccountable phenomenon which we might hope to influence in a desirable direction by such empirically developed practices as praise and blame, but whose specific actions we could generally not predict or control, because we could not obtain the information of all the particular facts which determined it.
Notice that this is not a claim about the world, but rather, a conditional response. Even if the world is deterministic, humans still face epistemic limitations and we must, as theorists, recognize this epistemic limitation. Even one's own mind must remin a mystery to oneself.
Hayek was not alone. The genius who shaped the modern world perhaps more than any other, John von Neumann, believed that Godel's theorem placed strict epistemic limits on self-understanding (Von Neumann 1966, 47):
I am twisting a logical theorem a little, but it's a perfectly good logical theorem. It's a theorem of Godel that the next logical step, the description of an object, is one class type higher than the object and is therefore asymptotically [?] infinitely longer to describe. I say that it's absolutely necessary; it's just a matter of complication when you get to this point.
He continues again, a few pages later:
The formal logical investigations of Turing went a good deal further than this. Turing proved that there is something for which you cannot construct an automaton; namely, you cannot construct an automaton which can predict in how many steps another automaton who can solve a certain problem will acutally solve it. . . . it is characteristic of objects of low complexity that it is easier to talk about the object than produce it and easier to predict its properties than to build it. But in the complicated parts of formal logic it is always one order of magnitude harder to tell what an object can do than to produce the object.
When the editor of the manuscript, Arthur W. Burks, inquired with Godel about this interpretation, Godel advised that:
what von Neumann perhaps had in mind appears more clearly from the universal Turing machine. There it might be said that the complete description of its behavior is infinite because, in view of the non-existence of a decision procedure predicting its behavior, the complete description could be given only by an enumeration of all instances. . . . The universal Turing machine, where the ratio of the two complexities is infinity, might then be considered to be a limiting case of other finite mechanisms. This immediately leads to von Neumann's conjecture.
This need for greater complexity pushes the scientist into what Hayek refers to a s a "pragmatic dualism". But perhaps this was not pragmatic at all. Observing the similarity of the two on this issue, Wiemer notes that "von Neumann saw it was also an epistemological necessity to have a duality of description for all phenomena - especially those involving life or living systems (2021, 17)." For fear that I am not being clear, I repeat, deterministic modeling does not vanquish uncertainty. And the resultant emergent phenomena require that we abandon attempts to explain the operation of those phenomena with no more then general reference to related patterns that appear in microfoundations.
We can add to our understanding that we can, at best, transition between states in a complex system probabilistically. The problem that this naturally entails is that the probabilities of state transitions are not typically derived from deduction as in apriori probability such as occurs with counting cards from a fair deck, but rather, must be inferred from a large number of observations, thus putting us in the realm of statistical probability. And we are always at risk of experiencing surprise with regard to statistical probability.
The system under observation might surprise the average observer or may not be correctly modeled either in the structure of the system analyzed or the nature of the distribution that is supposed to represent outcomes generated by the system. We may model incorrectly. Our samples may not be representative of the system. And classes of events that have never occurred before may simply be outside of the realm of modeling (those unknown unknowns, the simple categorization that made listeners of Donald Rumsfeld laugh).
We can add to this yet another epistemic problem: error in encoding and transmission of encodings. That is, not only do we face risk and uncertainty with regard to events that directly impact outcomes of concern to a modeler, but information itself is recorded imperfectly either due to corruption of data or lack of a perfect match between the container representing data and the event encoded. I will not elaborate this further. It is sufficient here to note the frame problem exists at every level that information is recorded.
Now, let's suppose that the frame problem does not exist. Here, I would like to focus on the problem of information corruption. While modern machines seem to operate perfectly, components of a digital computer deteriorate over time and under pressure of circumstance. Further, the medium through which digital messages are transmitted may promote error at some rate. Thus, finite state machines, when they function as desired, hide the pervasiveness of this problem. I do not propose a solution, but in thinking about the validity of the metaphor of the finite state machines, it is critical that we consider the kinds of variation that impact decisions of the machine.
The following exposition is intended to convey the prevalence of error that is faced by finite state machines that operate outside of simulation on a digital computer: i.e., the physical computers themselves. Programs on digital machines require that information be transmitted as zeros and ones: bits. Corruption of these will generate errors that, depending on the location of the corruption, can cause the program contained in the message to fail.
I will present a two layered solution to show the extent to which persistent corruption can be corrected using clever methods. It also conveys the extent to which factors promoting error can be hidden from an uninformed observer, despite their being pervasive. Of course, the observed order takes advantage of similar principles that limit the extent of corruption of information, namely redundancy. Thus, while a carefully constructed approach will here correct the error, we must ask ourselves what precisely underlies the order of the empirical world if life itself is dependent upon error correcting mechanisms? The explanatory power of deterministic modeling opens many question concerning disorder and its remedy. These are worth keeping in the back of one's mind during this exposition.
Claude Shannon, in his pathbreaking work on communication, notes that "by sending the information in a redundant form the probability of errors can be reduced (Shannon 1948, 410)." We will employ redundancy to reduce the rate of transmission error. Every message sent will be encoded three times in order to prevent corruption of a single bit from producing an incorect message. We will also use Hamming codes to produce excess bits with each message. These excess bits will allow us to correct a single corrupted bit for a unit of information transmitted. By unit, I refer to the number of bits required to transmit a message. For example, Shannon shows that a decimal number requires "about $3\frac{1}{3}$ bits". In practice, if you want to encode a decimal number in bits, this requires $4$ bits since the since we cannot depend upon a fraction of a bit (i.e., $2^3=8$ and $2^4=16$). Thankfully, for each additional bit included, the size of the number than can be contained by the set of bits doubles. So, to encode the number 100 requires $2^7$ ($128$) bits and to encode the number $1000$ requires $2^{10}$ ($1024$)bits.
We will encode a message, generate the helpful excess bits from the Hamming code, and then transmit three messages to take advantage of redundancy in reducing error transmission.
Our message is as follows:
ROSES ARE RED, VIOLETS ARE BLUE, IT'S SWEET WHEN THE HISTORY OF ECONOMICS OVERLAPS WITH THE HISTORY OF COMPUTER SCIENCE, AND SO ARE YOU!
We will take the set of characters and punctuation in this message and build an encoding scheme that maps each character onto a permutation of bits.
Once we take the set, we can identify the number of symbols that need to be mapped and, therefore, the size of the container that we will use to transmit the message. If we define the number of unique symbolsl as $x$, then we can round up $log_2(x)$ to identify the minimum number of bits required to encode the message.
import random
import math
import string
import numpy as np
poem = ("ROSES ARE RED, VIOLETS ARE BLUE, IT'S SWEET WHEN THE HISTORY OF ECONOMICS OVERLAPS WITH "
"THE HISTORY OF COMPUTER SCIENCE, AND SO ARE YOU!")
characters = set(poem)
num_chars = len(characters)
log_num_chars = math.log2(num_chars)
print(f"Number of unique characters: {num_chars}")
print(f"Log2 of number of characters: {log_num_chars}")
print("Taking log2 of the number of characters gives us the exponent to which 2 must be raised to get the number of characters.")
print("Rounding up give us the minimum number of bits needed to represent each character.")
bit_length = math.ceil(log_num_chars)
print(f"Number of bits per character: {bit_length}")
Number of unique characters: 24 Log2 of number of characters: 4.584962500721156 Taking log2 of the number of characters gives us the exponent to which 2 must be raised to get the number of characters. Rounding up give us the minimum number of bits needed to represent each character. Number of bits per character: 5
We gather a basic set of symbols that total to 24 different elements. To clarify why we take the log of the number of symbols, consider the following table:
| $$n$$ | $$2^n$$ |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
We can observe that $2^5$ is greater than the $24$ unique symbols that compose our message. So we will encode our letters and punctuation using $5$ bits. Each character is mapped to a unique $5$ bit encoding. This is arbitrary. What matters is that the recipient of the message follows the same standard for decoding.
In the resultant table, we read the values from top to bottom. Notice that the table counts up from 1 in binary ($00001$, $00010$, $00011$, etc...)
import pandas as pd
def pandasMaxColRow():
pd.set_option('display.max_column', None)
pd.set_option('display.max_rows', None)
pd.set_option('display.max_seq_items', None)
pd.set_option('display.max_colwidth', None)
pd.set_option('expand_frame_repr', True)
pandasMaxColRow()
mapping = {}
for i, char in enumerate(characters):
bit_str = format(i, f'0{bit_length}b')
mapping[char] = bit_str
mapping_df = pd.DataFrame(mapping.items(), columns = ['Character', f'{bit_length}-bit String'])
# unpack bit string across n columns
mapping_df = mapping_df.join(mapping_df[f'{bit_length}-bit String'].apply(lambda x: pd.Series(list(x))))
mapping_df.drop(f'{bit_length}-bit String', axis=1, inplace=True)
mapping_df.T
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Character | B | M | Y | U | ! | L | V | C | E | H | I | O | ' | S | F | R | , | W | P | A | N | D | T | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Now that the letters are encoded, we can send the message with each letter represented by 5 bits. Each bit is subject to some rate of corruption. Thus, we can model the distribution of outcomes using binomial probability.
Binomial Probability: $$P(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}$$
# use binomial distribution to simulate the error rate for triplet
# case where number of errors is 0, 1, 2, and 3
num_bits = 5
def binomial_probability(n, k, p):
return math.comb(n, k) * p**k * (1-p)**(n-k)
# error_rate is 1 - p
# 90% of bits transmitted will be correct; 10% will be corrupted
error_rate = 0.1
error_probabilities = {}
for i in range (num_bits + 1):
error_probabilities[i] = binomial_probability(num_bits, i, error_rate)
error_probabilities = pd.DataFrame(error_probabilities.items(), columns = ['Number of Errors', 'Probability']).round(6)
error_probabilities
| Number of Errors | Probability | |
|---|---|---|
| 0 | 0 | 0.59049 |
| 1 | 1 | 0.32805 |
| 2 | 2 | 0.07290 |
| 3 | 3 | 0.00810 |
| 4 | 4 | 0.00045 |
| 5 | 5 | 0.00001 |
For every $100$ $5$-bit packets sent, we expect only $59$ will not be corrupted. How can we reduce this rate of corruption? We will cover two methods. The most intuitive is to provide two reduntant bits for each bit in the original message. More bits could be used, but this increases the size of the message sent bya factor of $3$. For each bit, a new binomial logic applies. For each bit, our $l=3$ and we can ask, what is the probability that $n-l<2$? This is the probability that a bit will not be corrupted. (Remember, in our case each character is represented by $5$ bits.)
error_probabilities = {}
l = 3
for i in range (l+1):
error_probabilities[i] = binomial_probability(3, i, error_rate)
error_probabilities = pd.DataFrame(error_probabilities.items(), columns = ['Number of Errors', 'Probability']).round(6)
error_probabilities
| Number of Errors | Probability | |
|---|---|---|
| 0 | 0 | 0.729 |
| 1 | 1 | 0.243 |
| 2 | 2 | 0.027 |
| 3 | 3 | 0.001 |
Now, we can sum the probabilities of outcomes where the number of errors is less than half of $n$ (here $n=3$).
# correct encoding probability is sum of probabilities of 0 and 1 errors
correct_encoding_probability = error_probabilities[error_probabilities['Number of Errors'] <= 1]['Probability'].sum()
new_error_rate = 1 - correct_encoding_probability
print("\nProbability of correct encoding (up to 1 error):")
print(correct_encoding_probability)
print("Probability of incorrect encoding (2 or 3 errors):")
print(round(new_error_rate,3))
#probability of correct encoding over 5 binary values
correct_encoding_probability = (correct_encoding_probability)**bit_length
print(f"\nProbability of correct encoding of all {bit_length} binary values:")
print(correct_encoding_probability)
Probability of correct encoding (up to 1 error): 0.972 Probability of incorrect encoding (2 or 3 errors): 0.028 Probability of correct encoding of all 5 binary values: 0.8676235360696319
With triple encoding, we reduce the rate of error per bit from $10\%$ to $2.8\%$. We can recalculate the probability that a packet is corrupted using this new probability. Now, we expect that only 86.7% of messages will contain an error:
error_probabilities = {}
for i in range (num_bits+1):
error_probabilities[i] = binomial_probability(num_bits, i, new_error_rate)
error_probabilities = pd.DataFrame(error_probabilities.items(), columns = ['Number of Errors', 'Probability']).round(6)
error_probabilities
| Number of Errors | Probability | |
|---|---|---|
| 0 | 0 | 0.867624 |
| 1 | 1 | 0.124966 |
| 2 | 2 | 0.007200 |
| 3 | 3 | 0.000207 |
| 4 | 4 | 0.000003 |
| 5 | 5 | 0.000000 |
To better convey the point, lets create a function that creates triplets for each encoded bit:
def encode_triplet(message, mapping):
"""
For each character in the message, convert it to its 6-bit binary form,
then repeat each bit 3 times (e.g. '1' -> '111', '0' -> '000').
Characters not in the mapping are skipped.
"""
encoded_bits = ""
for char in message:
if char not in mapping:
continue # Skip any character not in our mapping.
bits = mapping[char]
for bit in bits:
encoded_bits += bit * 3 # Triple repetition for each bit.
return encoded_bits
encoded_bits = encode_triplet(poem, mapping)
print("\nEncoded bits with triple repetition:")
print(encoded_bits)
Encoded bits with triple repetition: 111000000000000000111111000000000111111111000000111000000111000111111111000000000000111000111000111000000111000000000000000111000000111000000000111000111000000000000000111000000111111000111111000111000000000111000000000111000000000111111111000111000111111000111111000000000000111111000000111000000111111000111111111000111111111000000000000111000111000111000000111000000000000000111000000111000000000111000000000000000000000000111111000000000111000000000111000000111111000000000111000000000111000000111000111111111000111111111000111111000111000111111111000000000000111000000111111111000111000000111000000111000000111000111000000111111000111111111000000000111000111000000111000000111000111000000111000000111111000111000111000000000111000111000111111111000111000111000000111000000111000000000111000000111000111000000111000111111000111111111000111000111111111000111111000000111000000000000000000000111111000000000111000000111111000000000111111111111000000000111000000111000000111000111000000000000111111000000111000111000111000111111000000000000000000111000111000111111000111000000000000111111111000000000000111000000111111000000000000111111111000111000000111111000000000000000000111111000111000111000000111000000111111000111111111000000000000111000111000000111000000111000111111111000111111111000111000111000000000000111000111000111111111000111000111000000111000000111000000000111000000111000111000000111000111111000111111111000111000111111111000111111000000111000000000000000000000111111000000000111000000111111000000000111111111111000000000111000000111000000000000111111000000000000000000111111000000111111000000111000000111000111111111000111000000111111000000000000000000000111000000111111111000000111000000000000111000111111000111000000111111000111000111000111000000000000111000000111111000000000111000000000111000111000111000000111000111000111111000111111000000000000111000000111111111000000111111000000000000000111000111000111000000111000000000000000111000000111000000000111000000000000111111000111111000000000000111000000000000111000111
Once encoded, we can simulate the transmission of the encoded bits over a noisy channel and check the over all rate of corruption of the encoded triplets.
def simulate_errors(encoded_bits, error_rate=0.005):
received_transmission = ""
for bit in encoded_bits:
if random.random() < error_rate:
bit = '0' if bit == '1' else '1'
received_transmission += bit
return received_transmission
def calculate_error_rate(original, received):
errors = sum(original[i] != received[i] for i in range(len(original)))
return errors / len(original)
received_transmission = simulate_errors(encoded_bits, error_rate=error_rate)
orig_percent_corrupted = 100 * calculate_error_rate(encoded_bits, received_transmission)
print(f"\nOriginal transmission corrupted by {orig_percent_corrupted:.2f}%")
Original transmission corrupted by 9.75%
Now, let's revise the received message by interpretting each encoded triplet according to the value that at least $2$ of the $3$ characters reflect. Remember, a single error in the transmission of the three bits composing a triplet will not corrupt the message. Remember, each bit is subject to this rate of error, so we expect that error in the decoded message would be much higher if there was no correction. Remember, we calculated that only $41\%$ of symbols would be corrupted with an error rate of only 10% per bit. We anticipate that the final decoded message should have a lower rate of error then the earlier calculated $41\%$:
# decode function
def majority_vote(triplet):
"""Return the bit (as a string) that appears at least twice in the triplet."""
return '1' if triplet.count('1') > triplet.count('0') else '0'
# decode function
def decode_triplet(encoded_bits, bit_group=3):
"""
Apply majority vote to every group of 3 bits to reverse triple redundancy.
"""
decoded_bits = ""
for i in range(0, len(encoded_bits), bit_group):
triplet = encoded_bits[i:i+bit_group]
if len(triplet) < bit_group:
continue
decoded_bits += majority_vote(list(triplet))
return decoded_bits
def decode_message(decoded_bits, mapping, bit_length=bit_length):
"""
Convert decoded bits into characters by grouping every bit_length bits
and mapping them using the inverse mapping table.
"""
inv_mapping = {val: key for key, val in mapping.items()}
message = ""
for i in range(0, len(decoded_bits), bit_length):
chunk = decoded_bits[i:i+bit_length]
if len(chunk) < bit_length:
continue
# Use '?' for any unknown bit sequence
# i.e., the encoded bits do not match any of the mapping
c = inv_mapping.get(chunk, '?')
message += c
return message
decoded_bits = decode_triplet(received_transmission)
decoded_message = decode_message(decoded_bits, mapping)
print("\nDecoded message:")
print(decoded_message)
decoded_triplet_error_rate = 100 * calculate_error_rate(poem, decoded_message)
print(f"Error rate after decoding triplets: {decoded_triplet_error_rate:.2f}%")
Decoded message: ROSES AAE RED, VIO ETS AREWBVUEM IT'S SWEET RHENBTHE HI?TORP OF ?BONO!ICS STEBLA?S WITH THE ISTORY OF C'!PUTER SCIINCE, ANT SC ARE YOU! Error rate after decoding triplets: 16.18%
Using a simple encoding strategy, we have made the error rate tolerable. The expected rate of error fell by greater than $20$ percentage points. With some background knowledge, the recipient on March 8 might think the attempt was sweet, but might also be let down that her admirer didn't reduce the rate of error.
If you want to reduce the rate of error, further you are in luck. We can still implement the Hamming code, which is a linear error-correcting code that can correct single bit errors. If one of the $5$ bits is incorrectly flipped, then the Hamming code will restore the incorrectly flipped bit to its original value. The Hamming code is a powerful tool that can be used to correct errors in data transmission. That is, if one of the $5$ bits is incorrectly flipped, then the Hamming code will restore the incorrectly flipped bit to its original value.
The Hamming code places parity bits at index values that are powers of $2$ (counting upward from $1$) so that the following equation is satisfied: $$2^r - 1 >= r + k$$ $$r: Parity\ Bits$$ $$k: Bit\ Length\ of\ Encoded\ Message$$
The code, $c$, is transmitted such that it can be multipied by a Hamming matrix where: $$s = Hc\ \%\ 2$$
The vector $s$ is a vector of $0s$ whose height is equal to the height of $H$. If $Hc$ does not yield a vector of $0s$, then the shortest transformation of $c$ that yields a vector of $0s$ is given precedence in the decoding process.
Let's compute the parity bits:
import random
import string
# Function to compute the number of parity bits required for a data block of length k.
def compute_num_parity_bits(k):
r = 1
# i.e., add 1 to r as long as 2**r not => k + r + 1
while 2**r < k + r + 1:
r += 1
return r
p = error_rate
k = bit_length
r = compute_num_parity_bits(k)
m = k + r
# check if the number of parity bits is correct
condition = 2**r >= m + 1
print("k:", k)
print("r:", r)
print("m:", m)
print("The condition that 2^r >= m + r + 1 is", condition)
k: 5 r: 4 m: 9 The condition that 2^r >= m + r + 1 is True
Now that we have calculated $r$ and $m$, we can proceed with encoding the message. The for loop follows the same logic. Each symbol is associated with encoded bitstring of the following form.
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Bit | $$p_1$$ | $$p_2$$ | $$d_1$$ | $$p_3$$ | $$d_2$$ | $$d_3$$ | $$d_4$$ | $$p_4$$ | $$d_5$$ |
Thus, vector $c$, our codeword, is: $$c = [p_1, p_2, d_1, p_3, d_2, d_3, d_4, p_4, d_5]$$
Each parity it is responsible for maintain either even or odd values for specific bit positions. These are called check sets. In the followin script, I have provided much in the way of notes and printed out helpful information for the very first symbol encoded in the process.
# Generalized Hamming encoder for a data block (as a string of bits).
def hamming_encode_block(data_block, first_char = False):
# 2^r >= k + r + 1.
k = len(data_block)
r = compute_num_parity_bits(k)
m = k + r
# Create a list for the codeword with indices 1..n (index 0 is unused).
codeword = [None] * (m + 1)
data_index = 0
# Place data bits in positions that are NOT powers of 2.
for i in range(1, m + 1):
if (i & (i - 1)) == 0: # i is a power of 2: reserved for parity.
codeword[i] = '0' # temporary placeholder (will compute parity later)
else:
codeword[i] = data_block[data_index]
data_index += 1
# Compute each parity bit.
for p in range(1, m + 1):
# p is a parity bit position.
# One way to think about this is that p + p - 1 yield all 1s in the binary representation.
# p = 1 --> 1 + 0 = 1 (1 + 0)
# p = 2 --> 10 + 1 = 11 (2 + 1)
# p = 3 --> 100 + 11 = 111 (4 + 3)
# p = 4 --> 1000 + 111 = 1111 (8 + 7)
if (p & (p - 1)) == 0:
parity = 0
# For every position j from 1 to n, if the p-th bit of j is 1, include its bit.
for j in range(1, m + 1):
if j & p:
if first_char and j!=p:
# use first character enchoding to clarify the parity bit calculation
print(f"j={np.binary_repr(j)} ({j}) and p={np.binary_repr(p)}({p}) both have a 1 at position {p}")
# ingore if j is the parity bit, since by definition both have 1 at position p
if j == p:
continue
# if the bit is 1, then add it to the parity calculation
# i.e., 0 and 1 yield 1; 1 and 1 yield 0; 0 and 0 yield 0; 1 and 0 yield 1
parity ^= int(codeword[j])
# after adding is completed across all j positions, the parity bit is set to the result
codeword[p] = str(parity)
if first_char:
for parity_bit_index in range(1, r + 1):
print(f"Parity bit {parity_bit_index} keeps the sum of values even for the following indices:")
parity_set = []
for data_bit_index in range(1, m + 1):
if data_bit_index & (1 << (parity_bit_index - 1)):
parity_set.append(data_bit_index)
print(parity_set)
print(f"\n[p_1, p_2, d_1, p_3, d_2, d_3, d_4, p_4, d_5]:\n{codeword[1:]}")
# transform list of bits into a string
return "".join(codeword[1:])
# Encode an entire message using Hamming codes.
def encode_message_hamming(message, mapping):
encoded = ""
first_char = True
# cycle through each character to generate the Hamming code for each character
for char in message:
if char not in mapping:
continue
data_bits = mapping[char]
codeword = hamming_encode_block(data_bits, first_char)
encoded += codeword
first_char = False
return encoded
encoded_bits = encode_message_hamming(poem, mapping)
print("\nEncoded bitstring (generalized Hamming code):")
print(encoded_bits)
print(f"Length of poem: {len(poem)} characters")
print(f"Length of encoded bitstring: {len(encoded_bits)} bits")
print(f"Length of encoded bitstring per character: {len(encoded_bits) / len(poem):.2f} bits/char")
j=11 (3) and p=1(1) both have a 1 at position 1 j=101 (5) and p=1(1) both have a 1 at position 1 j=111 (7) and p=1(1) both have a 1 at position 1 j=1001 (9) and p=1(1) both have a 1 at position 1 j=11 (3) and p=10(2) both have a 1 at position 2 j=110 (6) and p=10(2) both have a 1 at position 2 j=111 (7) and p=10(2) both have a 1 at position 2 j=101 (5) and p=100(4) both have a 1 at position 4 j=110 (6) and p=100(4) both have a 1 at position 4 j=111 (7) and p=100(4) both have a 1 at position 4 j=1001 (9) and p=1000(8) both have a 1 at position 8 Parity bit 1 keeps the sum of values even for the following indices: [1, 3, 5, 7, 9] Parity bit 2 keeps the sum of values even for the following indices: [2, 3, 6, 7] Parity bit 3 keeps the sum of values even for the following indices: [4, 5, 6, 7] Parity bit 4 keeps the sum of values even for the following indices: [8, 9] [p_1, p_2, d_1, p_3, d_2, d_3, d_4, p_4, d_5]: ['1', '1', '1', '0', '0', '0', '0', '0', '0'] Encoded bitstring (generalized Hamming code): 111000000110011000000111100000110011000111100110100100101101000111000000000110011110100100111000000000110011011001100011000011110100100000001111110010111110011000100001100000110011111001111000111100110100100101101000111000000000110011110100100000000000100001100010101000000110011011000011110100100110010111111001111010011011000111100110100100000111100001100100000110011000110011111001111110100100001100100010010100000110011001101011110100100111001111010010100000110011110100100010010100110010111000111100111001111110011000111000000010100111110100100110011000100111111110100100000110011100110000110011000001101011110011000100000011110010111100110000000111100110100100110011000000001111000110011111000000100001100101101000101100111000111100110100100001100100110010111111001111010010100110100100111001111010010100000110011110100100010010100110010111000111100111001111110011000111000000010100111110100100110011000100111111110100100100110000110011000100000011101100111010101000111001111000110011111000000110100100000111100100110000110010111000110011001101011100110000000110011011000011110100100101101000001101011011001100110100100000111100110011000110100100101101000111000000000110011110100100010100111110011000010101000110101011 Length of poem: 136 characters Length of encoded bitstring: 1224 bits Length of encoded bitstring per character: 9.00 bits/char
The Hamming matrix is of dimensions $r \times m$ where $r$ is the number of parity bits and $m$ is the length of the encoded message. Each column in the matrix counts upward from $1$ in binary form. In the case that each symbol is encoded using $5$ bits, the number of parity bits is $4$. The length of the Hamming codeword is $9$. Thus the Hamming matrix is: $$ H = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & \\ \end{bmatrix} $$
For each encoded symbol, to yield the vector s, which should be a vector of zeros (of length four in this case), we take the vector of: $$Hc\ \%\ 2$$
If the result is a vector of zeros, then the encoded message is correct. If the vector $s$ contains non-zero values, then the next step is to determine the position of the error by converting the binary representation of s to decimal form. The position of the error is the decimal representation of $s$. For example, if $s = [0, 1, 1, 1]$, then the error is in position 7. The error would be corrected by flipping the bit in position 7.
def hamming_decode_block(codeword):
# each codeword is a string of bits that represents an encoded symbol
m = len(codeword)
# Determine all parity positions (those that are powers of 2, 1-indexed)
parity_positions = []
i = 1
while i <= m:
parity_positions.append(i)
i *= 2
r = len(parity_positions)
# transform string of bits to an array of bits
c = np.array([int(b) for b in codeword]).reshape(m, 1)
# Build the parity-check matrix H of size (r x m)
# Each column j (for j = 1,..., n) is the binary representation of j (with r bits) in little-endian order.
H = np.zeros((r, m), dtype=int)
for j in range(1, m+1):
# Get the binary representation of j with r bits (MSB first)
bin_rep = format(j, f'0{r}b')
# Reverse to little-endian order (so row 0 corresponds to bit value 1)
bin_rep = bin_rep[::-1]
for bit_index in range(r):
H[bit_index, j-1] = int(bin_rep[bit_index])
# Compute the syndrome: s = H * c (mod 2)
syndrome_vector = np.mod(H.dot(c), 2)
# Convert the syndrome vector to an integer using little-endian order.
syndrome = 0
for bit_index in range(r):
syndrome += syndrome_vector[bit_index, 0] * (2 ** bit_index)
# Convert codeword to a 1-indexed list.
bits = [None] + [int(b) for b in codeword]
# If syndrome is nonzero, it indicates the error position (1-indexed).
if syndrome != 0 and syndrome <= m:
# Correct the error by flipping the bit at the index of the syndrome value converted to decimal.
bits[syndrome] ^= 1
# Extract the the bits that map to the symbols (i.e., non-parity bits)
data_bits = ""
for j in range(1, m+1):
if j not in parity_positions:
data_bits += str(bits[j])
corrected_codeword = "".join(str(b) for b in bits[1:])
return corrected_codeword, data_bits
# Simulate transmission errors by flipping bits with independent probability error_rate.
def simulate_errors(bitstring, error_rate=0.005):
corrupted = []
for bit in bitstring:
if random.random() < error_rate:
corrupted.append('0' if bit == '1' else '1')
else:
corrupted.append(bit)
return "".join(corrupted)
# Decode a received bitstring using the generalized Hamming decoder.
def decode_hamming_bits(received_bits, data_length):
r = compute_num_parity_bits(data_length)
block_length = data_length + r
decoded_data = ""
for i in range(0, len(received_bits), block_length):
block = received_bits[i:i+block_length]
if len(block) < block_length:
continue
_, data_bits = hamming_decode_block(block)
decoded_data += data_bits
return decoded_data
# Simulate transmission errors.
# 0.5% chance to flip each bit.
corrupted_bits = simulate_errors(encoded_bits, error_rate)
print("\nCorrupted bitstring (after transmission errors):")
print(corrupted_bits)
# Decode the received bitstring.
decoded_bits = decode_hamming_bits(corrupted_bits, bit_length)
decoded_message = decode_message(decoded_bits, mapping, bit_length)
print("\nDecoded message:")
print(decoded_message)
Corrupted bitstring (after transmission errors): 111000001100011100000101000000110010000111100110100100101101001110000000000111011110100100111010000000110010111001100011000010110100000000001111111010111110011001100001100000110011111001111000111100010100100101101000111000000000110001100110110000001000100001110011111010000110011011100011110100110110010111111001101011011011000111100110101100000111100101100101001110010000110000111001011110100100101100100010010100000110011011101011110100100111001110000110100000010011110000100010000000110010011000111100111001111010001000111000100010100011110100100110011001100011111111100000000111011100111000010011000001101010110001000100000011110010110100110010100011100100100100110011000000001101000110011011000000100001100101101000101000100000111100010100101101100110110010111111001111010110100010100101111001111010010100000110111110110100010010100110011111000111100111001011110011010111000010110100111010100101110011000100101111110100100110110000110011000100000011101100111010100000111001111000110011111000000100100100000111100100111000110010111010111101001101011101110000000110010001000011100001100100101001010101111011001100110100100000111100010011000110100101001101000111000000010110011110100100010100111100011000001111000110000011 Decoded message: RLUES ARE RED, VIOLETS AREHBL?E, IT'S SP?CT WHEN TSE BISTURY OFRECONOMICL OVERLA?SYPITHYTHE HISTORYYOF COMPUTER SCIFNCE,L!YD SO ARE YO?M
# Calculate the percentage of correct characters in the decoded message.
hamming_error_rate = calculate_error_rate(poem, decoded_message)
print("Error Rate:", round(100 * hamming_error_rate, 2), "%")
Error Rate: 16.91 %
The result is not great, but it is still an improvement over the rate of error of $41\%$ that we would otherwise expect.
If we combine the methods, we vastly improve the outcome. We will first encode the hamming matrix. Then, we will create triplets for each bit of the Hamming codeword. If one or fewer of these triplet bits is corrupted, then, the codeword will not be corrupted after identifying each bit according to the majority of values within a triplet. However, if 1 bit within the codeword is still corrupted, meaning that one of the triplets in a codeword had 2 or more bits flipped, this error can still be corrected after decoding the triplets during the decoding of the Hamming matrix.
def encode_triplet_from_bits(bits):
"""
Convert the binary bits into characters using the mapping,
then apply triple redundancy encoding.
"""
triplet_bits = ""
for bit in bits:
triplet_bits += bit * 3
return triplet_bits
def decode_triplet(encoded_bits, bit_group=3):
"""
Apply majority vote to every group of 3 bits to reverse triple redundancy.
"""
decoded_bits = ""
for i in range(0, len(encoded_bits), bit_group):
triplet = encoded_bits[i:i+bit_group]
if len(triplet) < bit_group:
continue
decoded_bits += majority_vote(list(triplet))
return decoded_bits
# -----------------------------------------
# Combined encoding: Triplet encoding is applied first, then Hamming encoding.
encoded_hamming = encode_message_hamming(poem, mapping)
encoded_hamming_triplets = encode_triplet_from_bits(encoded_hamming)
# simulate transmission errors
corrupted_hamming_triplets = simulate_errors(encoded_hamming_triplets, error_rate)
decoded_hamming_triplets = decode_triplet(corrupted_hamming_triplets)
decoded_hamming_block = decode_hamming_bits(decoded_hamming_triplets, bit_length)
decoded_message = decode_message(decoded_hamming_block, mapping, bit_length)
hamming_triplet_error_rate = calculate_error_rate(poem, decoded_message)
print("Error Rate:", round(100 * hamming_triplet_error_rate, 2), "%")
print(decoded_message)
j=11 (3) and p=1(1) both have a 1 at position 1 j=101 (5) and p=1(1) both have a 1 at position 1 j=111 (7) and p=1(1) both have a 1 at position 1 j=1001 (9) and p=1(1) both have a 1 at position 1 j=11 (3) and p=10(2) both have a 1 at position 2 j=110 (6) and p=10(2) both have a 1 at position 2 j=111 (7) and p=10(2) both have a 1 at position 2 j=101 (5) and p=100(4) both have a 1 at position 4 j=110 (6) and p=100(4) both have a 1 at position 4 j=111 (7) and p=100(4) both have a 1 at position 4 j=1001 (9) and p=1000(8) both have a 1 at position 8 Parity bit 1 keeps the sum of values even for the following indices: [1, 3, 5, 7, 9] Parity bit 2 keeps the sum of values even for the following indices: [2, 3, 6, 7] Parity bit 3 keeps the sum of values even for the following indices: [4, 5, 6, 7] Parity bit 4 keeps the sum of values even for the following indices: [8, 9] [p_1, p_2, d_1, p_3, d_2, d_3, d_4, p_4, d_5]: ['1', '1', '1', '0', '0', '0', '0', '0', '0'] Error Rate: 2.94 % ROFES ARE RED, VIOLETS ARE BLUE, IT'S SWEET WHEN THE HISTORY OF ECONOMICS OVERLAPS WITH THE HISTORY OF COMPUTNR SCIEN?E, AND SOHARE YOU!
What fantastic progress we have made! And just imagine that, in order for life to exist, let alone human life, similar sorts of error correction must occur over the course of organisms living and as new organisms are created. And we have conveniently constructed containers in this example that exactly match the symbols referenced. I haven't elaborated the means by which such containers of information can be created in the first place! Perhaps the human nervous system - what AI researchers refer to as a subsymbolic system - lends insight into the precise means by which encoded information sufficiently coheres to the environmental phenomenon encoded. But that is beyond my aim here. Even if a system is deterministic, there is sufficient mystery in the chasm between emergent phenomena and their constituent parts to limit claims derived by deterministic models. Add to this problems of probability and errors in encoding, and the honest scientist should be filled with humility.