The Multiple Dimensions of Codes

code-computer-cyberspace-225769

How do we ensure a message sent to a Mars Rover is received correctly, diminish the impact of information technology on the environment, and reduce the degradation of stored data? Solutions can, in part, be found in error-correcting codes which encode, pad out, or extend data in such a way that it becomes possible to inspect the encoded data later, finding and fixing any errors that have been introduced.

Robert Bailey and Daniel Hawtin are currently conducting work on combinatorics and group theory (the study of symmetry), and applications in error-correcting coding theory.

‘Coding,’ in this case, does not refer to codes used for secret messages but to how to make a message more likely to be understood or correctly received.

When data needs to be protected against corruption, or when a transmission needs to be sent to a receiver that can’t be physically accessed such as the receiver on a space probe or Mars rover, message length is highly important. Restricting message length is key to maintaining speed but needs to be balanced with maintaining accuracy. For example, sending a message in code multiple times would benefit accuracy, but would consequently reduce speed.

Restricting message length, and increasing efficiency, also means saving power which decreases the environmental impact of sending and storing data.

citrus-food-fruits-53371 (1)

Oranges and Binary Strings

In the case of binary code this may mean limiting a line of ones and zeros (or binary string), to a certain length (i.e. 011100011), and then analyzing the line mathematically.

Each component in the length of a message can be seen mathematically as a dimension in a conceptual space, and this conceptual space can then be used to analyse the message. For example, a binary string 011 would have three dimensions when being analyzed, where as the binary string 01110110111 would have eleven dimensions.

Within these ‘spaces’ mathematicians pack spheres with code words at the center of each, kind of like packing oranges into a box (although a box with a potentially unlimited number of dimensions). The spheres (the oranges in the box), and the internal relationships of their respective code words, are key to accurately analyzing codes, and that is where Bailey and Hawtin’s work comes in.

The researchers are looking at the symmetries of the way the spheres are packed, a key aspect to their effectiveness. Hawtin describes the process as follows:

“Say I want to send a ‘no’ or a ‘yes’, which we might represent as ‘0’ and ‘1’. Then a very simple way to encode these two messages, and allow for error correction, is as ‘000’ and ‘111’, respectively. So, we are simply repeating the message three times.

If the data is later read/received as ‘001’, ‘010’ or ‘100’ then we assume one error has occurred and ‘no’ was the intended message. Similarly, if ‘011’, ‘101’ or ‘110’ is read/received then we assume that one error has occurred, but this time that the intended message was ‘yes’. Otherwise, we assume that no errors have occurred and that the message received was the intended one.

Although this increases the integrity of the stored/transmitted data, the problem here is that we are storing/sending three times as much data. So we need to find codes that give an optimal balance between the integrity of the encoded data and this increase in the size of the data.

There are two ‘oranges’ in the above example. The first, associated to the message ‘no’, is: ‘000’, ‘001’, ‘010’, ‘100’. The second, associated to the message ‘yes’, is ‘111’, ‘011’, ‘101’, ‘110’. Notice that there are no other binary strings of length three, so these two ‘oranges’ perfectly fill the entire ‘box’ they are stored in.”

190px-Hamming_distance_3_bit_binary.svg.png
Image from en:User:Cburnett

From the 1860s to the Voyager Space Probes

Group theory is the study of algebraic structures called ‘groups.’ Bailey and Hawtin’s work looks at symmetries in terms of dots (in this case the code words) and connections between dots, using graph and group theory, and how these dots can move around while still preserving the connections between them.

“The idea is that if somebody wants to have a code for communication with a certain amount of symmetry then you can use abstract mathematical results to give all the possible codes with a certain type of symmetry,”

states Bailey,

“the weaker idea of symmetry, which is combinatorial symmetry is how we used to study these things. But the new idea is to define symmetry conditions on your codes, and then classify these using powerful results from group theory.”

This is an area of research with a long past and an exciting future. The 24-dimensional Golay Code is one notable example of these coding practises and was used in communications to the Voyager 1 and Voyager 2 space probes which are now hurtling towards interstellar space. But the Golay code has a long history. The Mathieu groups, which are the algebraic objects describing the symmetry of the Golay codes, were first discovered in the 1860s and 70s, long before space exploration or the invention of digital computers. These arose as part of an abstract study of symmetry, that originally had no specific application in mind, but are of theoretical interest due to their high degree of symmetry.

The Grenfell Campus researchers are actively pursuing the new avenues available in this dynamic topic of study.

Written and edited by Conor Curtis; Additional editing by Daniel Hawtin and Robert Bailey

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s