Is Morse Code binary, ternary or quinary?

Question Detail: 

I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says:

Morse code is said to be a binary (literally meaning two by two) code because the components of the code consists of only two things - a dot and a dash.

Wikipedia on the other hand says:

Strictly speaking it is not binary, as there are five fundamental elements (see quinary). However, this does not mean Morse code cannot be represented as a binary code. In an abstract sense, this is the function that telegraph operators perform when transmitting messages (see quinary).

But then again, another Wikipedia page includes Morse Code in 'List of binary codes.'

I am very confused because I would think Morse Code actually is ternary. You have 3 different types of 'possibilities': a silence, a short beep or a long beep.

It is impossible to represent Morse Code in 'stirct binary' isn't it?

By 'strict binary' I mean, think of stream of binary: 1010111101010.. How am I supposed to represent a silence, a short beep and / or a long beep?

Only way I can think of is 'word size' a computer implements. If I (and the CPU / the interpreter of the code) know that it will be reading 8 bits every time, then I can represent Morse Code. I can simply represent a short beep with a 1 or a long beep with a 0 and the silences will be implicitly represented by the word length.(Let's say 8 bits..) So again, I have this 3rd variable/the 3rd asset in my hand: the word size.

My thinking is like this: I can reserve the first 3 bits for how many bits to be read, and last 5 bits for the Morse code in a 8bit word. Like 00110000 will mean 'A'. And I am still in 'binary' BUT I need the word size which makes it ternary isn't it? The first 3 bits say: Read only 1 bit from the following 5 bits.

Instead of binary, if we use trinary, we can show morse code like: 101021110102110222 etc.. where 1 is: dit 0 is: dah and 2 is silence. By using 222 we can code the long silence, so if you have a signal like *- *--- *- you can show it like: 102100022210, but it is not directly possible using only with 1's and 0's UNLESS you come up with something like a 'fixed' word size as I mentioned, but well this is interpreting, not saving the Morse Code as it is in binary. Imagine something like a piano, you have only the piano buttons. You want to leave a message in Morse Code for someone and you can paint buttons to black. There is no way you can leave a clear message, isn't it? You need at least one more color so you can put the silences (the ones between characters and words. This is what I mean by trenary.

I am not asking if you can represent Morse Code in 57-ary or anything else.

I have e-mailed the author (Charles Petzold) about this; he says that he demonstrates in Chapter 9 of "Code" that Morse Code can be interpreted as a binary code.

Where am I wrong with my thinking? Is what I am reading in the book, that the Morse Code being a Binary a fact or not? Is it somehow debatable? Why is Morse Code is told be quinary in one Wikipedia page, and it is also listed in List of Binary Codes page?

Edit: I have e-mailed the author and got a reply:

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

From: "Charles Petzold"

To: "'Koray Tugay'"

Subject: RE: Is Morse Code really binary? Date: 3

Mar 2015 23:04:35 EET

Towards the end of Chapter 9 in "Code" I demonstrate that Morse Code can be interpreted as a binary code.

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

I am not hiding his e-mail as it is really easy to find on the web anyway.

Asked By : Koray Tugay

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39920

Answered By : babou

Morse code is a prefix ternary code (for encoding 58 characters) on top of a prefix binary code encoding the three symbols.

This was a much shorter answer when accepted. However, considering the considerable misunderstandings between users, and following a request from the OP, I wrote this much longer answer. The first "nutshell" section gives you the gist of it.

Contents

• In a (big) nutshell
• Codes: basic points
• Codes: definitions
• The Morse code
• Analysing the three levels of representation
• Remarks on this analysis
• The importance of analog to logical transition
• Conclusion

In a (big) nutshell

When asking "Is Morse Code binary, ternary or quinary?" there is no comparing possible answers unless one fixes some criteria for an acceptable answer. Indeed, without proper criteria, one can contrive explanations for nearly any kind of structure. The criteria I have chosen are the following:

• it should reflect the three-tiered description of Morse-code with the dot/dash representation in the second tier;

• it should fit the presentation and mathematical tools developed for the theoretical analysis of codes, as much as possible;

• it should be as simple as possible;

• it should clearly make apparent the properties of the Morse code.

This is intended to preclude arbitrary hacking, that ignores basic concepts of code theory as scientifically studied, and which may have some appeal by giving an illusion of systematic analysis, though addressed too informally to be conclusive. This site is supposed to be about computer science, not programming. We should use a minimum of established science and accepted concepts to answer a technical question.

A quick analysis of the standard shows that all symbols used in Morse code are ultimately coded in binary, since it is transmitted as a string of units of equal length, whith a signal that can be on or off for each unit. This indicates that Morse messages are ultimately coded in a logical alphabet $\Sigma_1=\{0,1\}$.

But that says nothing of the internal structure of the code. The information to be encoded is a string on an alphabet of 58 symbols (according to the standard) including 57 characters and a space. This corresponds to an alphabet $\Sigma_3=\{A,B,\dots,Z,0,1,\dots,9,?,=,\dots,\times,@,[\;]\}\;$, the last symbl being the space.

However, the standard specifies that there is an intermediate alphabet $\Sigma_2$, based on dot and dash and possibly other symbols. It is quite clear

• that strings in $\Sigma_3^*$ are to be coded as strings in $\Sigma_2^*$, and

• that strings in $\Sigma_2^*$ are to be coded as strings in $\Sigma_1^*$

So, given that there is no choice for $\Sigma_1$ and $\Sigma_3$, the question must be understood as: "What number of symbols should we consider in the intermediate alphabet $\Sigma_2$ so as to best axplain the structure and the properties of the whole Morse code," which also entails specifying the two encodings between the three levels.

Given the fact that the Morse code is a prefix homomorphic (variable length) code that precludes any ambiguity when decoding a signal, we can explain simply this essential property with a ternary alphabet $\Sigma_2=${dot, dash, sep}, and two coding scheme $C_{3\to 2}$ from $\Sigma_3$ to $\Sigma_2$, and $C_{2\to 1}$ from $\Sigma_2$ to $\Sigma_1$, which are both homomorphic and prefix, thus both unambiguous codes, and thus able to be composed to give an unambiguous prefix encoding of the 58 symbols into binary.

Hence Morse code is composed of a prefix ternary code expressed in the alphabet $\{$ dot, dash, sep $\}$**, with these three symbols themselves encoded in binary** with the following codewords:

dot $\to 10$, dash $\to 1110$, and sep $\to 00$

Note that what is known as the space between consecutive dot or dash is actually included in the representation of dot and dash, as this is the usual mathematical representation for such types of codes, which are usually defined as string homomorphisms from source symbols to codewords expressed with target symbols, as I just did.

This departs a little from some of the presentation given in the standard, which aims more at specifying intuitively the code for users, rather than at analysing it for its structural properties. But the encoding is the same in both cases.

Even without the precise timings of the standard, a decoder of the analog signal could still translate it into the ternary alphabet we suggest, so that the above understanding of the ternary code would still be valid.

Codes: basic points

This answer is based on the Standard ITU-R M.1677-1, dated October 2009 (thanks to Jason C for the reference). I shall use the terminology dot and dash, rather than dit and dah, as it is the terminology used by this standard.

Before we start discussing the Morse code, we need to agree on what a code is. The difficult discussions on this question obviously requires it.

Fundamentally, information needs to be represented in order to be transmitted or otherwise processed. A code is a system to translate information from one system of representation into another. This is a very general definition. We must be careful not to confuse the concept of a representation, and that of a code from one representation (the source) to another (the target).

A representation can take many forms, such as variable electric voltage, colored dots on paper, string of characters, numerals, binary strings of 0's and 1's, etc. It is important to distinguish between analog and formal (or logical, or abstract) representation.

An analog/physical representation is a drawing, a varying voltage level, a shape (for a letter).

A logical/formal/abstract representation is a mathematical representation with abstract graphs, strings of symbols, or other mathematical entities.

Though some information may originally be analog, we usually convert it to a logical representation so as to be able to define precisely its processing by mathematical means, or by people.

Conversely, we dealing with logical representation using physical devices, such as computer or transmitters, we need to give an analog form to the logical representation.

For the purpose of this analysis, the only analog form we consider is that used for transmission, as described in the standard. But even then, we will consider that the first step is to interpret this analog representation as a direct implementation of an identically structured logical representation, on which we build our analysis of what kind of code Morse code may be. Code theory is a mathematical body of knowledge based on the analysis of logical representations.

However we shall come back on the analog/logical transition in the discussion at the end.

Codes: definitions

Our logical view is that the code is used to translate sources strings on an source alphabet $S$ to a target alphabet $T$. It is often the case that both alphabets are identical, usually binary, when the purpose is to add some extra property to the representation of information, such as making it more resistant to errors (error detection and correction), or making the representation smaller by removing redundancy (lossless code compression) and possibly with carefully controled loss of some information (lossy compression).

However, the purpose of Morse code is to provide only a way to represent strings on a large alphabet, into strings based on a much smaller alphabet (actually binary), using an intermediate alphabet almost binary (dots and dashes) to better adapted to human perception and manipulative abilities. This is achieved by what is called variable-length code:

Using terms from formal language theory, the precise mathematical definition is as follows: Let $S$ and $T$ be two finite sets, called the source and target alphabets, respectively. A code $C: S \to T^*$ is a total function mapping each symbol from $S$ to a sequence of symbols over $T$, and the extension of $C$ to a homomorphism of $S^*$ into $T^*$, which naturally maps each sequence of source symbols to a sequence of target symbols, is referred to as its extension.

We call codeword the image $C(s)\in T^*$ of a symbol $s\in S$.

A variable-length code $C$ is uniquely decodable if the corresponding homomorphism of $S^*$ into $T^*$ is injective. That means that any string in $T^*$ can be the image of at most one string in $S^*$. We also say that the code is unambiguous, meaning that any string can be unambiguously decoded, if at all.

A variable-length code is a prefix code if no codeword is the prefix of another. It is also alled instantaneous code, or context-free code. The reason for these names is that, when reading a target string that begins with a codeword $w$ of a prefix code, you recognize the end of the codeword as soon as you read its last symbol, without having to know/read the next symbol. As a consequence, prefix codes are unambiguous and very easy to decode fast.

It is easily shown that unique decodability and the prefix property are closed under composition of codes.

Note that the definition as a homomorphism implies that there is no special separation between codewords. It is their structure, such as the prefix property, that allows identifying them unambiguously.

Indeed, if there were such separation symbols, they would have to be part of the target alphabet, since they would be necessary to decode string from the target alphabet. Then it would be quite simple to revert to the theoretical model of variable-length code by appending the separator to the preceding code word. If that were to raise contextual difficulty (due for example to multiple separators), that would only be a hint that the code is more complex than apparent. This is a good reason to stick to the theoretical model described above.

The Morse code

The Morse code is described in the standard at three levels:

• 3 . it is intended to provide an encoding of natural language text, using 57 characters (27 letters, 10 digits, 20 synbols and ponctuations) and an inter-word space to cut the character string into words. The inter-word space is used like a special character, that can be mixed with the others, which I shall note SEP.

• 2 . all of these characters are to be encoded as successions of dash and dot, using an inter-letter space, which I shall note sep, to separate the dash and dot of one letter from those of the next letter.

• 1 . The dash and dot, as well as sep are to be encoded as signal or absence of signal (called spacing) with length precisely defined in terms of some accepted unit. In particular, the dash and dot encoding a letter must be separated by an inter-element space, that I shall note σ.

This already calls for a few conclusions.

The message to be transmitted and received in analog form is a successions of length units (space length or time length), such that a signal is on of off for the whole duration of each unit as specified in the Annex 1, Part I, section 2 of the standard:

2   Spacing and length of the signals 2.1 A dash is equal to three dots. 2.2 The space between the signals forming the same letter is equal to one dot. 2.3 The space between two letters is equal to three dots. 2.4 The space between two words is equal to seven dots. 

This is clearly an analog encoding in what is known as a bit stream, which can be logically represented in binary notation by a string of 0 ans 1, standing for the analog off and on.

In order to abstract away issues related to analog representation, we can thus consider that Morse code messages are transmitted as bit strings, that we shall note with 0 and 1.

Hence the the above excerpt from the standard can be expressed logically as:

• 0 . A dot is represented by 1.
• 1 . A dash is represented by 111.
• 2 . An inter-element space σ is represented by 0.
• 3 . An inter-letter space sep is represented by 000.
• 4 . An inter-word space SEP is represented by 0000000.

So we could see Morse code as using 5 code words in binary to encode these 5 symbols. Except for the fact that this is not quite how the system is described, there is some more to it, and it is not the most convenient way it can be thought of, from a naive or a mathematical point of view.

Note also that this description is intended for laymen, not code theory specialists. For that reason it describes more the visible appearance than the internal structure that justifies it. It has no reason to preclude other descriptions that are compatible with this one, though mathematically more structured, to emphasize the properties of the code.

But first, we should note that the complete description of the code involves 3 levels of representation, immediately recognizable:

• 3 . The text, composed of a string of characters, including SEP.
• 2 . The encoding of a letter string as a string of dot, dash and sep.
• 1 . The encoding of a level 2 string of these three symbols as a binary string.

We may possibly discuss as to what symbols is encoded in what, but it is an essential aspect of Morse code that it has these three levels of representation, with characters at the top, dots and dashes in the middle, and bits 0 and 1 at the bottom.

This implies that there are necessarily two codes, one from level 3 to level 2, and the other from level 2 to level 1.

Analysing the three levels of representation

In order to have a consistent analysis of this 3-tiers coding system, we should first analyse what kind of information is relevant at each level.

• 1 . The bit string, by definition, and by necessity of its analog representation, is composed only of 0 and 1.

• 3 . At the text level, we need and alphabet of 58 symbols, including the 57 characters and the inter-word space SEP. All 58 of them have to have ultimately a binary encoding. But, though the Morse code standard specifies these 57+1 characters, it does not specifies how they should be used to encode information. That is the role of English and other natural languages. The Morse code provides other system with an alphabet of 58 symbols, on which they could build some 58-ary code, but Morse code is not itself a 58-ary code.

• 2 . At the dot and dash level, all we need is these two symbols in order to code the 57 characters, i.e. provide a codeword for each as a string of dot and dash, together with some separator sep to mark when one letter finished, and another start. We also need some means of encoding the inter-word space SEP. We might try to provide for it directly at leavel 1, but this would mess-up the otherwise tier-structured organization of the code.

Indeed, the description of the standard might rightly be criticized for doing just that. But the authors may have thought that their presentation would be simpler to grasp for the average user. Also it follows a traditional description of Morse code, that predates this kind of mathematical analysis.

This calls for several remarks:

• at level 3, the letter level, the inter-letter space sep is no longer meaningful. This is quite normal, since it has no more meaning in the universe of letters than the space separating two written characters on paper. It is necessary at level 2 to recognize codewords representing the letters, but that is all.

• similarly at level 2, the inter-element space σ is no longer meaningful. It has no meaning in the world of dot and dash, but is only necessary at level 1 to identify the binary code words representing dot, dash. But at level 1, it is not distinguishable from the bit 0.

So the inter-element space σ is no longer anything special. It is just one use of 0.

However, as explained previously, if the code $\Sigma_2^*\to\Sigma_1^*$ is to be analyzed using knowledge of variable length codes, separators should be appended into the codewords they follow, so as to define the code as a simple string homomorphism.

This implies the following partial specification of the code: dot$\to$`10` and `dash`$\to$1110

The level 2 alphabet $\Sigma_2$ needs at least one other symbol, the inter-letter space noted sep, which should be 000 according to the letter of the standard. However, the definition of the variable length code as a homomorphism required appending the inter-element space 0 to each codeword for dot and dash. Hence we must have only 00 as codeword for sep, so that toghether with the ending 0 from the preceeding dot or dash, it makes 3 0 as required by the standard. This always work since there is no provision in the standard for having two inter-letter separators following each other.

This is enough to encode the alphabet $\Sigma_2=${dot, dash, sep} with a homomorphic code $C_{2\to 1} : \Sigma_2\to\Sigma_1^*$ defined as follow:

• dot$\to$10

• dash$\to$1110

• sep$\to$00

And we have the good surprise to discover that no codeword is a prefix of another. Hence we have a prefix code, which is unambiguous and easy to decode.

We can now proceed similarly to define the code $C_{3\to 2}: \Sigma_3\to\Sigma_2^*$.

The standard uses strings of dot and dash as codewords for the characters in $\Sigma_3$, in the way given by the tables of the standard for example dot dot dash dot to represent the letter $f$.

Again, these codewords are separated by inter-letter spaces. In order to define the code as a homomorphism, we must include the separator in the codewords, so that the definition of the homomorphism becomes rather: $f\to$ dot dot dash dot sep

This applies to each of the 57 characters in the alphabet $\Sigma_3$. But again we also need the word separator SEP, which, according to the standard, is 0000000. We first note that already 3 bits 0 are provided by the code, 2 by the sep that ends the last letter of the word, and 1 by the 0 bit that end the last dot or dash of the encoding of that last letter. Hence SEP must ultimately be coded as the remaining 0000.

But to respect the tiered approach, SEP should be encoded in some codeword from $\Sigma_2^*$. Since sep is binary encoded as 00, it follow that SEP can be encoded as sep sep.

Hence we can encode the alphabet $\Sigma_3=\{A,B,\dots,Z,0,1,\dots,9,?,=,\dots,\times,@,$ SEP$\}$, with a homomorphic code $C_{3\to 2} : \Sigma_3\to\Sigma_2^*$ defined as follows:

• $A \to$ dot dash sep

• $B \to$ dash dot dot dot sep ...

• $Z \to$ dash dash dot dot sep ...

• $7 \to$ dash dash dot dot dot sep ...
• SEP $\to$ sep sep (for the word separator)

And we have the further surprise to see that no codeword is a prefix of another. Hence the code $C_{3\to 2}$ is a prefix code too.

Since the prefix property is closed under composition of codes, the Morse code $C_{Morse}= C_{2\to 1}\circ C_{3\to 2}$ is a prefix code.

We can thus conclude that the Morse code can be understood, and easily analyzed, as the composition of a prefix binary encoding of a 3 symbols alphabet {dot, dash, sep} into a binary alphabet, and a prefix encoding of a 58 symbol alphabet (57 characters and one space) into the 3 letters alphabet.

The composition itself is a prefix encoding of the 58 symbols into a binary representation.

Remarks on this analysis.

It is always difficult to establish that a presentation of a structure is the best one can come up with. It seems however that the above analysis meets the criteria set up at the beginning of this answer: closeness to the 3-tiered definition, formally presented according to current coding theory, simplicity, and evidencing the main properties of the code.

Note that there is little point in looking for error correction properties. The Morse code may not even detect a single bit error as it may simply change two dot into one dash. However, it causes only local errors.

Regarding compression, the ternary encoding was designed to approximately reduce the number of dots and dashes, in an approximative kind of Huffman coding. But the two composed codes could easily be made denser.

Regarding the size of alphabets, there is no choice for the binary and the 58 symbols alphabet. The intermediate alphabet could contains more symbols, but what would be the purpose?

However, some people would be inclined to recognize the space DET at level 2, thus making the alphabet quaternary, then using it directly at level 3, encoded as itself in level 2.

This would meet the standard definition, for DET encoded in binary as 0000. But it would prevent the analysis of the binary encoding $C_{2\to 1}$ as a prefix code, making it harder to show that $C_{Morse}$ is a prefix code, hence unambiguous.

Indeed, such a choice would make the binary string 0000 ambiguous, decodable as either SEP or as sep sep. The ambiguity would have to be resolved with a contextual rule that sep cannot follow itself, making the formalization more complex.

The importance of analog to logical transition.

This analysis relies heavily on the fact that the decomposition of the on/off signal into units of equal lengths indicates clearly an analog representation of a binary string. Furthermore, the lengths in units are exactly right for the above analysis, which seems unlikely to have happened by chance (though it is possible).

However, from a (too cursory) look at the original patent 1647, it does not seem to have been that precise, with sentences such as (on top of page 2):

The sign of a distinct numeral, or of a compound numeral when used in a sentence of words or of numerals, consists of a distance or space of separation between the characters of greater extent than the distance used in separating the characters that compose any such distinct or compound numeral.

People who were later sending by hand or receiving by ear were also unlikely to be that precise either. Indeed, their fist, i.e. their timing, was often recognizable. This view is also supported by the fact that spacing lengths are not always respected, particularly when learning Morse code.

These situations correspond to an analog view of the code as short signal (dot), medium signal (dash), and short, medium and long pause. Direct transposition into a logical alphabet would naturally give a quinary alphabet, into which the 58 symbols have to be coded. This of course is no longer a 3-tiered presentation of the Morse code.

However, in order to make sense (and possibly avoid ambiguity), this alphabet should be used with the constraint that two signal symbols (dot or dash) cannot follow each other, and that pause symbols cannot follow each other either. Analysis of the code and its properties would be made more complex, and the natural way to simplify it would be to do what was done: introduce proper timings to turn it into the composition of two codes, leading to the fairly simple analysis given above (remember that it includes showing the code is prefix).

Furthermore, it is not strictly necessary to follow exact timings in the analog representation. Since the decoder of the analog translation can distinguish short, medium and long pauses, by whatever means, it should just mimic what was done in the binary case. Hence short and medium signal (necessarily followed by a pause) are recognized as logical dot or dash. Short pauses are forgotten, as only serving to mark the end of dot or dash. Medium pauses are recognized as sep, and long pauses are recognized as two sep in succession. Hence the analog signal is represented in a ternary alphabet, which can be used as before to encode the 58 symbols alphabet. Our initial analysis can be used even when timings are not strictly respected.

Alternatively, the signal-pause alternance could be used to turn this quinary alphabet into a ternary one, keeping only the three durations as symbols of the alphabet, and using contextual analysis to determine whether a given duration is signal or pause. But this is again a bit complex to analyze.

This just shows that there are many ways to look at things, but they are not necessarily convenient, and may not all lend themselves easily to analysis with the mathematical tools that have been developed to analyze codes.

More references to the patents can be found on the Internet.

Conclusion

Given the precise timings of the standard, a good answer seems to be to consider Morse code as the composition of a ternary prefix encoding (of 58 characters) into a 3 symbols alphabet, composed with a binary prefix encoding of these three symbol.

Without the precise timing of the standard, the binary level can no longer be considered. Then the analog to logical decoding naturally takes place at the level of the intermediate alphabet of dot and dash. However, the analog to logical decoder can stil decode to the previous 3 symbols alphabet, thus preserving the applicability of our analysis.