26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please move any further conversation to chat.stackexchange.com/rooms/21638/… $\endgroup$ – Wandering Logic Mar 4 '15 at 16:15
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Mar 5 '15 at 8:16
  • $\begingroup$ I fixed the links I accidentally deleted (whoops); please refrain from any more rolling back to worse revisions. $\endgroup$ – Raphael Mar 5 '15 at 9:05
  • 1
    $\begingroup$ @WanderingLogic The correct, most effective and noise-free approach is to silently flag the question for comment cleanup and suggest comments be moved to chat in the flag, not to publicly play comment police and attempt to create a chat room to combine all comments on all answers with no context. Your links also now just confuse the matter since Raphael has posted correct links. $\endgroup$ – Jason C Mar 5 '15 at 9:49
  • 1
    $\begingroup$ @J.-E.Pin Well, I did not give a formal definition because I took for granted that people answering the question would know that, and I did have a reference or two to wikipedia to set the context. Even if wikipedia can be far from perfect, this should be able to take the role of definitions, as often done here. It took me some time to realize that it was the problem, actually apparently widespread. I was myself in the process of rewriting it all at length, with explicit definitions, quotes, references and formal explanations with injective homomorphisms. Should I finish? $\endgroup$ – babou Mar 7 '15 at 20:28
19
+150
$\begingroup$

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

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.

$\endgroup$
  • 1
    $\begingroup$ Please move any further conversation to chat.stackexchange.com/rooms/21638/… $\endgroup$ – Wandering Logic Mar 4 '15 at 16:16
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Mar 5 '15 at 8:17
  • $\begingroup$ Question: In the ternary argument you start with an alphabet {0,1}, from this you construct four symbols {dot=10,dash=1110,sep1=00,sep2=000000}, from this you construct a ternary code word set by allowing sep2=sep1 sep1 sep1. The code word set was chosen because it implicitly ties the symbols to the encoding, which is convenient, and the OP is asking about binary storage. However, why can't you instead use code word set {rest=0,on=1} then say "dot=on", "dash=on on on", sep0="off", sep1="off off off", sep2="off off off off off off off" (where sep0 is intersignal rest)? $\endgroup$ – Jason C Mar 6 '15 at 15:02
  • $\begingroup$ ^ In which case the argument is for a binary code word set over a ternary one, but using a similar and equally strong argument as the ternary one given here. That is, the choice to give special meaning to multiple separators in a row but not give special meaning to multiple anything-else in a row is fundamental to the ternary argument, but also seems arbitrary. $\endgroup$ – Jason C Mar 6 '15 at 15:04
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – babou Mar 7 '15 at 18:26
28
$\begingroup$

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...

Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five it is based on your application and the encoding requirements for your specific situation. To that end, there are pros and cons to each symbol set size, which you should consider for your situation before making a decision.

For the basis, M.1677, the international Morse Code standard, section 2, defines timings as:

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.

Note that that defines timings only, e.g. a dash does not mean the same thing as three dots, it is simply the same length. The base unit of time is a dot.


Binary

We can choose binary if we'd like. It is possible to represent Morse Code with "strict binary", as you call it -- that author's approach was to assign the digits to "dot" and "dash". That approach does not work and I do not think the author has a firm grasp of Morse code. But there is a different approach that works. If we choose binary, we essentially represent whether the signal is high or low with each symbol occupying a single dot-lengthed time slice. Note that this is also the approach described on the List of Binary Codes page you cited.

Other binary codings can be chosen as well (e.g. Bob Jarvis' answer) at the expense of increases in difficulty decoding back to audible Morse Code (Bob's encoding cannot be decoded statelessly, for example, the tradeoff is it provides shorter encoded sequences).

Symbols:

  • Low, off, etc. (0)
  • High, on, etc. (1)

Encoding Examples:

  • Signal separator: 0
  • Letter separator: 000
  • Word separator: 0000000
  • Three dots: 10101
  • Three dashes: 11101110111
  • The word "son": 101010001110111011100011101
  • The phrase "is a": 10100010101000000010111

Pros:

  • Minimal symbol set size
  • Easily managed with typical digital logic
  • Easy to decode into audible Morse Code (presuming no validation is done); stateless decoding and does not require storing information about the timing of symbols (every symbol is the same length).

Cons:

  • Long encodings.
  • Many opportunities for invalid encodings.
  • Individual symbol meanings (0, 1) depend on context.


Ternary

With this choice, we define letter and word spacings as rests, and signal spacings are implicit (although you could choose to require dot length rest symbols between signals, if it suits you better).

Symbols:

  • Dot-length rest (0)
  • Dot (1)
  • Dash (2)

Encoding Examples:

  • Letter separator: 000
  • Word separator: 0000000
  • Three dots: 111
  • Three dashes: 222
  • The word "son": 11100022200021
  • The phrase "is a": 11000111000000012

Pros:

  • Small symbol set size.
  • Signal separator no longer needed.
  • Shorter encoding lengths than binary.
  • Removes some invalid encodings (e.g. 0110 with the binary choice no longer possible).

Cons:

  • Still lengthy encodings.
  • Still many possibilities for invalid encodings, in particular, the rests.
  • Cannot be decoded statelessly unless you choose to place explicit dot length rests between signals.
  • Signal separators are implicit unless you choose to place explicit dot length rests between signals.
  • Some individual symbol meanings (0) depend on context.


Quaternary

Symbols:

  • Letter separator (0)
  • Word separator (1)
  • Dot (2)
  • Dash (3)

Encoding Examples:

  • Three dots: 222
  • Three dashes: 333
  • The word "son": 2220333032
  • The phrase "is a": 220222123

Pros:

  • Very short encoded length.
  • Possibility of invalid encodings is reduced.
  • Symbols are semantically accurate.
  • Arguably, more human-readable.

Cons:

  • Large symbol set size.
  • Cannot be decoded statelessly.
  • Signal separators are implicit.


Quinary

A direct interpretation of Wikipedia's list. Note this is very similar to the binary choice except the various valid combination of binary 0's or 1's are given their own symbols.

Symbols:

  • Signal separator (0)
  • Letter separator (1)
  • Word separator (2)
  • Dot (3)
  • Dash (4)

Encoding examples:

  • Three dots: 30303
  • Three dashes: 40404
  • The word "son": 303031404041403
  • The phrase "is a": 3031303032304

Pros (compared to quaternary):

  • Can be decoded statelessly.
  • The only symbol set size that unambiguously, directly and concisely represents the five objects mentioned in section 2 of the standard: "dot" (to which all timings are relative to), "dash", "space between the signals", "space between two letters", "space between two words".

Cons (compared to quaternary):

  • Higher possibility for invalid encodings.
  • Increased encoding lengths without adding extra information (tradeoff is decoding ease).
  • Not as easy to decode as the binary choice, in that each symbol is a different length in time and this association must be maintained somewhere.


57-ary:

Included for completeness.

Symbols:

  • 26 letters
  • 10 numbers
  • 20 punctuation marks and miscellaneous signs
  • Word separator (space)

Encoding Examples:

  • The word "son": son
  • The phrase "is a": is a

Pros:

  • Shortest encoding
  • Human readable
  • Invalid encodings are impossible.

Cons:

  • Largest symbol set
  • Difficult to decode into Morse Code; necessary to maintain tables of Morse Code output sequences for each symbol and necessary to detect word boundaries and adjacent letters to determine where to insert various rests.
  • Impossible to expand beyond the Morse Code specification without adding new symbols (tradeoff for being immune to invalid encodings).
  • Signal and letter separators are implicit.

Termination

For storage as a symbol stream on a device, if you need to do that, it's worth noting that M.1677 defines message and transmission termination sequences. From Part II:

5 Every telegram shall be terminated with a cross signal (. – . – .)
6 The end of the transmission shall be indicated by the cross signal (. – . – .) followed by the invitation to transmit signal K (– . –)
7 The end of work shall be indicated by the station that transmitted the last telegram. The correct indication is the end of work signal (. . . – . –)

Unfortunately, the standard is silent on the ability to distinguish e.g. the string "+K" from the sequence (end-of-telegram, invitation-to-transmit). However, end-of-work is unique. If you are storing morse code, then, you will have to make a choice as to how you want to indicate the end of a stored sequence.

If you are storing an entire conversation, for example, and are using the binary symbol set, you could reasonably consider end-of-work to be the end of sequence indicator, represented as the unique bit sequence 101010111010111. You need to consider the type of data you are storing (e.g. message fragments, entire messages, entire conversations) as well as the facilities offered to you by your storage medium (e.g. ability to prefix with message length) before deciding. I suppose you could go so far as to define your own end of sequence indicator. In any case these are all matters of underlying storage and have too many possibilities to list here. The choice is really up to you based on whatever is appropriate for your situation.


Cannot be decoded statelessly: These encodings require some state to be maintained in order to decode into audible Morse Code. They all require "If preceding symbol was a dot/dash and current symbol is a dot/dash then insert signal separator". While you could try and "cheat" and automatically append a signal separator to all symbols while reducing word separator to 5 rests and letter separator to 1, M.1677 afaict does not explicitly prohibit consecutive word separators, which breaks this kludge.

Signal separators are implicit: This is directly related to the above note but more semantically oriented. These encodings have implicit signal separators in their notation. That is "zzz" is intuitively three separate z's, the boundaries are "piggybacked" on whatever it is that separates symbols in the encoding itself. Consider the description "three dots in a row"; intuitively we take this to mean three separate dots, but if separators weren't implied this could be taken to be indistinguishable from a dash. Only the Wikipedia-style binary and quinary (or ternary with the explicit signal separator option) representations remove all ambiguity and "shortcuts" here, which can be of great value depending on the situation. It is for this reason that there is a strong argument for the quinary choice.


TL;DR:

As you can see, there are advantages and disadvantages to each, and it's up to you to decide how you want to treat it based on your requirements. There is no right answer. You could attempt to argue that one is more appropriate than the other in general, but these arguments would boil down to pedantic preferences, as without context, there is no correct answer.

Now, all that said, in my own opinion, the quinary choice is the representation that feels the most "right" to me for Morse Code itself (originally I had favored quaternary). It is the only choice that provides all of the following:

  • Context-free symbols (a symbol on its own contains all information about its meaning without examining adjacent symbols).
  • Representation of all primitives defined in M.1667.
  • Separators (signal, letter, word) are not implied by notation or underlying encoding (this is important, if I wrote { dot, dot, dash }, those ,'s are significant and easy to overlook).

However, there are strong arguments for all. The arguments related to encoding are also applicable to the treatment of Morse itself. There is no 100% concrete answer, but it can certainly make a good topic for debate with your friends at the bar.

. . . – . –

$\endgroup$
  • 1
    $\begingroup$ Please move any further conversation to chat.stackexchange.com/rooms/21638/… $\endgroup$ – Wandering Logic Mar 4 '15 at 16:16
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Mar 5 '15 at 8:16
  • $\begingroup$ You keep referring to stateless decoding in your arguments. In coding theory, states seem to be used only rarely, in convolutional codes, which are a family of error correcting codes. This is completely off-topic as Morse code is anything but error correcting. Indeed, it cannot even detect some one bit errors, let alone correct them. You contrive various kinds of arbitrary codes as being a version of Morse code, but they bring no understanding. Why present them? Not requiring states, i.e. homomorphic encoding, seems a minimum requirement. And you miss the interesting encodings. cc @KorayTugay $\endgroup$ – babou Mar 6 '15 at 11:34
  • $\begingroup$ @babou Statless decoding arguments? $\endgroup$ – Koray Tugay Mar 6 '15 at 11:52
  • $\begingroup$ @babou I don't mind having a couple off-topic points. Of course the symbol sets are arbitrary; that's precisely the point I'm making with this answer. The ternary word set on top of binary prefix code argument is equally arbitrary. At first glance no, but fundamentally, you made the arbitrary choice to base the argument on a code word set with a two letter alphabet (0 and 1). It is an arbitrary choice, because the choice to give "sep sep sep" special meaning but not do that to a "unit 1" is arbitrary. You could just as easily say that "dash" is "dot dot dot" and argue for binary over ternary. $\endgroup$ – Jason C Mar 6 '15 at 15:16
5
$\begingroup$

Despite my initial thoughts on this, it turns out this question can be formalized in a way that admits a fairly precise answer (modulo a couple of definition issues). The answer turns out to be 3 or 4, i.e. ternary or quaternary. The crowd-pleaser "everything goes from 2 to 57" answer is correct only in the sense that if someone asks you for a characterization of abelian groups, you tell him they are sets.

Let's start by looking at the physical encoding for Morse code. That's actually BASK, i.e. binary amplitude-shift keying, which is just an elaborate way o saying there two physical (electrical/optical etc.) amplitude levels for us to encode our message. So, the immediate question is: doesn't this mean that answer is that Morse code is binary? Well, it's binary only in a rather non-informative way, in the sense that the binary on/off signal sent over the wire doesn't correspond directly to either lines or dots. At this vague level of correspondence, we could even send the ASCII code (with the direct, obvious bit encoding) and call it "Morse" and/or "binary"; the same would apply to any Huffman code (instead of ASCII).

So how can we make the correspondence more precise and at the same time formalize our question? Coding theory comes to help. Let $M$ be the set of "morsable" symbols, roughly 66 symbols if I understand the Morse code universe correctly; this includes the 26 Latin letters, the 0-9 digits, and a bunch of ancillaries like some punctuations, "prosigns" etc. It's actually not terribly important what these are. A code is an injective mapping $c:M\to T^*$ where $T$ (not $T^*$) is a set of codewords. To be physically representable in our underlying BASK hardware, we require that $T\subset \{0,1\}^*$, i.e. our codewords need to be a strings of bits; note that this entails $c$'s values are strings of codewords, so strings of strings of bits, but ultimately linearized as just strings of bits.

To be a faithful characterization of Morse code, we need $T$ to contain some direct equivalents of lines and dots, in the sense that there must be a bijection between these codewords and the dots and lines representing Morse code on paper. $T$ is also required to be [almost] a uniquely decipherable code, meaning that any factoring of an element of $T^*$ in terms of elements/codewords of $T$ [ideally] must be unique. (Note that some authors, e.g. Berstel, don't even call $T$ a code unless it is uniquely decipherable, but others, e.g. Steve Roman have a different terminology where any mapping is a code, but those that are uniquely decipherable are just said so and abbreviated UD codes. Here I'll just the latter terminology. You'll also see a bit later why I said "ideally".)

Since $c$ is only required to be an injection and not a surjection, we can populate $T$ with arbitrary "junk" beyond what's needed to get a UD code, as long as the strings generated by this junk aren't the preimage of anything morsable. For example, a string of exactly 42 dots doesn't correspond to anything in any variant of Morse code I saw. So when when we ask if the Morse code binary, ternary, quaternary, quinary etc., the question should is asking for the minimal cardinality of $T$ with the above two properties, i.e.: it is [almost] an UD code and we have an obvious bijection between the paper-based "line" and "dot" to some elements of $T$.

There a two ways to proceed in constructing $T$, either top-down by observing that you need a separator between the paper-based, line-dot representation of Morse letters in order to get a UD code, or bottom-up since in the ITU international Morse code we're given the time-lengths of the lines, dots, and various pauses. I'll use the latter approach here because there are numerous ways to get some $T$ otherwise, i.e. you can pick fairly arbitrary time-lengths, e.g. the defunct American Morse code used shorter lines than the ITU version.

Start let's with the ITU signal-length-derived representation which has five basic codewords, generated from the unit-length "on" signal (1) and "off" signal (0): just-dot (1), just-line (111), unit-space (0), letter-space (000), and word-space [assumed seven 0's in the International Morse but can vary in practice]. Immediately note that the unit-space can only appear followed by a 1 only right after just-dot and just-line; and this $0$-termination of just-dot and just-line (which is a comma code; more on this later) is actually required otherwise you couldn't even tell apart lines from dots. This gives you the obvious reduction to four codewords with:

  • dit = just-dot unit-space = 10 and
  • dah = just-line unit-space = 1110.

So that's the quaternary Morse code: dit, dah, letter-space, word-space. The next observation is that the word-space can be approximated (or even assumed to be) two letter-spaces, i.e. six zeros. So how that's how you get the ternary codeword set; As references for this line of reasoning see e.g. [1] [2].

There is also a technical reason to prefer the ternary codewords: $T = \{10 , 1110, 000\}$ is a uniquely decipherable code, in fact it is a prefix code. However $\{10 , 1110, 000, 0^7\}$ (or the version with just six zeros) is no longer uniquely decipherable because $0^{10}=0^30^7=0^70^3$ so there's a non-unique factorization. While this is theoretically a problem, it is of no practical concern because the human "metronome" has difficulty measuring very long silences anyway, so basically any silence longer than a certain length is assumed (by a human) to be a word-space of sorts.

Also note that if you stick $0$ in that set too (i.e. take "quinary" view), it gets "even more wrong", in the sense that even $000$ no longer has unique factorization (as itself is a code word too). Furthermore, $0$ is not in the preimage of any Morse symbol, so it is junk in $T$, much like you can add $1^{42}0$ to $T$; in fact adding the latter is less troublesome as unlike adding $0$ it won't make the code lose the UD property.

The reduction/abstraction from dit, dah, letter-space as binary codewords to three abstract symbols (trits) is useful for showing quickly that the (ternary) Morse code is UD; that's immediately obvious because letter-space acts as a comma, i.e. the ternary Morse code is a comma code. (Note that other authors define "comma code" in a more restrictive sense where all symbols other than the comma are the same one; I'm using it here in the wider sense given in D.H. Smith's "Post-modern algebra", which just means using a unique terminating symbol for ever codeword.) Also note that the comma0code technique is used at two levels in the Morse code; the just-line and just-dot are terminated by the "short comma" unit-space=$0$ to make them distinguishable from each other. Once you abstract that construction to the two different (dit and dah) trits, all the Morse code letters are also comma-coded by terminating them with $000$ which the third trit.

You can also use the trit approach calculate entropy assuming a dah and dit and letter-space are "equivalent" as trits [3], in the sense that—for example—'e' takes 2 trits and 'y' takes 5 trits. The abstract trit approach is not so useful if you care about how expensive each symbol is to actually transmit in the real BASK Morse encoding on a line. For the latter, you need to get down to the real bit lengths of the 3 (or 4) symbols, which are seen as just as transitions in an automaton. For instance the letter 'e' takes 5 bits to encode (as dit letter-space) while 'y' takes 17 bits (three dahs, one dit and a letter-space). This line of thinking goes back to Shannon (see pp. 3-4). More details can be found in Blahut's "Information Theory and Coding", e.g. he calculates "an average of 9.296 units of signaling time per source output letter" for Morse code using the (unconditional) probabilities of letter occurrences in English. For a slightly different exposition (by a zoologist!) you could look at J.P. Hailman's; he gets a different average (10.2) because he assumes slightly different probabilities for English letters, but otherwise his analysis is conceptually the same.

To summarize this: you can take several views of the Morse code, but some are more fruitful than others in saying anything interesting about it. I'm not aware of any analyses using the "quinary" view and in order for this model to not be reducible to four symbols you'd have to make some assumptions about the occurrence the unit-space that don't hold in actual Morse, e.g. that you could have two but not necessarily three adjacent unit-spaces (which is invalid Morse). The ternary view buys you a quick analysis of the unique decodability. The most deep/fruitful view is the one which sees the 3 or 4 symbols as actually represented by unequal amounts of bits as they are in the real Morse code (|dit|=2, |dah|=4, |letter-space|=3 and |word-space|=6 or 7); it's still insightful at this low-level to consider the ternary/quaternary symbols as transitions in an automaton.

As to why Wikipedia sucks on this... well on some topics it just does. Their main article on http://en.wikipedia.org/wiki/Coding_theory is not really something I'd recommend reading either. I can't say much about the (Petzold) book you've mentioned other than it doesn't appear written by an expert in information theory. Petzold is correct only in the sense that if Morse-coded messages consisted of only one letter you could reasonably say they are in some binary code; if you want to send words though, you need a letter separator, otherwise the code would be horribly not UD, to the point of impracticality.


It's a bit late here for me to revise the entire post, but @babou makes a valid point below that apparently Shannon, Blahut and others have misinterpreted the (current) ITU standard (assuming it hasn't changed since their time) in the following technicality: the unit space is added between dits and dahs of the same letter, but only the letter-space is added between letters. This reading of the standard seems to check out based on a fairly recent practitioner's book. So we need to borrow one 0 from letter-space into each dit and dah when they are in terminal positions of a letter, leaving only two 0's for the letter-space, i.e. $T=\{10, 1110, 00\}$. That also means that (for example) the size of 'e' is only 4 bits, not 5.

$\endgroup$
-1
$\begingroup$

Originally Morse code was intended to be written marks on a strip of paper, but telegraph operators soon became able to "read" the clicks of the equipment. This version of Morse (American or "land" Morse) had three "mark" elements, the dot, the dash, and the long dash.

The use of International Morse during the last century, via radio transmission, was usually encoded by hand (on a telegraph key) and decoded by ear, by listening to the pattern of beeps produced by the receiver. Skilled operators could receive better than unskilled ones, and some people could produce code that was easier to understand than that of others. A good transmitting operator was said to have a "good fist." An inept operator was called a LID. (For the origin of "lid" -- which I believe comes from a common error in American Morse of sending LID for DD, daaahh, dit dit, dah dit dit instead of dah dit dit, dah dit dit -- see this reference: https://english.stackexchange.com/questions/31818/how-did-the-word-lid-come-to-mean-poor-operator-in-the-context-of-telegraph .)

Thus it follows that the "encoding" of Morse into a binary format depends upon purpose, and thus whether the quality of "good fist" versus "poor fist" is to be retained. Is a string of on-and-off switching to be matched to a clock and "corrected" for difficulties in phase or duration of each portion of the signal? Or is it instead to be sampled at a rate sufficient to retain random or confusing variations, presumably for later inspection or delight?

$\endgroup$
  • 1
    $\begingroup$ Sorry, how does this answer the question? $\endgroup$ – Koray Tugay Mar 2 '15 at 12:08

protected by Wandering Logic Mar 4 '15 at 16:17

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.