Distance of Characters

We look at the effect of a bitwise change in the representation of characters. When transmitting data it might happen that one bit changes during transmission. Here we investigate this effect and calculate sets of “reachable” characters. So, here we look at the German alphabet und make use of the concept of Entities in Mathematica (here the Entity German Language), which can be entered via keyboard by pressing “Shift”+“Ctrl”+“Enter”

These are the letters that can be found on the keybord of a German computer:

But these are only the lowercase letters, we get the uppercase ones quickly:

Now we detect, that there is no oppercase “ß” (by the way such a character exists). So we delete the “SS” whcih can be found in the list of uppercase letters:

Lowercase letters

First we are going to examine the neigborhood in the lowercase letters. We therefore use the lowercase German letters:

We start with character “a”:

The objective is to get a function which can be iterated to determine all characters that are reachable starting with the startcharacter (her the letter “a”), an collecting in each step all direct neighbors, i.e. the ones with a (Hamming-) distance 1 to “a”.

The next function determines all characters of distance 1 from the given character, and delivers al list of neighbors.

Now we can easily determine the neighbors of “a” and get the result in the form , where the are the neighbors of *c*

Visualizing the result (remeber: we take in account only lowercase letters):

0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |

0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |

0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |

0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |

0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |

The next function takes a list of neighbors and makes a list of neighbors in the same matter as above:

In the last step we process a list of such neighbors (resp. neigborlists), the application of union filters out all duplicates

Now we can use the built in function Nest to get all neighbors of e.g. degree three

In the next step we have to build rules for each neighborhood, to make it possible to plot a corresponding graph. Here we make use of the outer “product”. First we look at one element of our neighbourhoodlist

Now we can see how “outer” works:

Finally it is easy to built a graph:

Do the plotting:

One can brush up the graph using the options “EdgeRenderingFunction” and “VertexRenderingFunction”:

Putting the parts together we build a funtion to plot the graph of desired order directly

The reachable characters

Now let´s have a look how many characters are reachable, when doing always a 1-Bit-distance step. This can easily calculated:

So

The number of reachable characters can now easyly visualized:

As we see the process of iteration is going to get stationary at a certain point. But unfortunately not all characters are within reach of “a”. This can easily be seen when looking at the number of characters within reach of “a”:

but

So we miss two characters. To look a bit closer at this effect we define the (bitwise) Hamming-distance of two characters:

Now we can calculate the maximum Hamming distance, measured bitwise, in our set of letters. Therefore we build up all pairs of characters, calculate the distance and take the maximum:

This may need a word of explantion:

Tuples[letters,2] determines all pairs of letters from the set letters

The command @@@ replaces all the heads inside the list of tuples (which is “List”) with “hammingDistanceChar”, which calculates the Hamming distance between these chars

finally Max does what it should: I calcualtes the maximum of all this numbers

So we hava a maximum distance of 6 between the letters. But as we have seen two characters are missing in the reachable characters. Let´s look what characters these are:

So we know that these characters are not reachable from startcharacter “a” when we assume one Bit changes in each step. This means clearly, that there is “the other way round”, no way outside fom these two characters:

The two characters have a distance of three, when bitwise calculated, so these characters are not “reachable” in the case that always (only) one bit changes at a time.

Word - Distances

Init