Intergalactic Transmission
Send a message seven bits to a byte, each byte ending in a parity bit that makes its count of ones even, and decode a transmission back, rejecting a byte whose parity is wrong.
Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.
// FILE: intergalactic_transmission.nomi
//# Sends a message as bytes with a parity bit each, and reads it back.
/// The bytes that carry `message`: its bits seven at a time, the last seven
/// padded with zeros, each followed by a parity bit that makes the byte's
/// count of ones even.
//! assert transmit([0x05]) == [0x05, 0x81]
//
pub fn transmit(message: List<Int>) -> List<Int>
message
|> Iter.flat_map(bits)
|> Iter.chunks(7)
|> Iter.map(fn chunk ->
// The last chunk may be short: zeros pad it to seven bits.
data = Iter.concat(chunk, Iter.repeat(0)) |> Iter.take(7) |> Iter.to_list() |> from_bits()
data <<< 1 + Iter.sum(chunk) % 2
end)
|> Iter.to_list()
end
/// The message `transmission` carries: the seven data bits of each byte,
/// eight at a time, with the bits left over at the end dropped. A byte whose
/// count of ones is odd was damaged on the way, and is `Err("wrong parity")`.
//! assert receive([0x05, 0x81]) == Ok([0x05])
//
pub fn receive(transmission: List<Int>) -> Result<List<Int>, String>
data =
transmission
|> Iter.map(data_bits)
|> Result.collect()?
data
|> Iter.flatten()
|> Iter.chunks(8)
|> Iter.filter(&(Iter.count(&1) == 8))
|> Iter.map(from_bits)
|> Iter.to_list()
|> Ok()
end
/// The first seven bits of `byte`, or an error when its parity is odd.
fn data_bits(byte: Int) -> Result<List<Int>, String>
all = Iter.to_list(bits(byte))
if Iter.sum(all) % 2 == 0 then
all |> Iter.take(7) |> Iter.to_list() |> Ok()
else
Err("wrong parity")
end
end
/// The eight bits of `byte`, most significant first.
fn bits(byte: Int) -> Iter<Int>
Iter.map(0..8, fn i -> byte >>> (7 - i) &&& 1)
end
/// The number whose bits, most significant first, are `bits`. Every bit is
/// a 0 or a 1, so each is a digit of base 2.
fn from_bits(bits: List<Int>) -> Int
Int.from_digits(bits, 2)!
end
// FILE: intergalactic_transmission_test.nomi
import intergalactic_transmission.{receive, transmit}
test "calculate transmit sequences"
[
("empty message", [], []),
("0x00 is transmitted as 0x0000", [0x00], [0x00, 0x00]),
("0x02 is transmitted as 0x0300", [0x02], [0x03, 0x00]),
("0x06 is transmitted as 0x0600", [0x06], [0x06, 0x00]),
("0x05 is transmitted as 0x0581", [0x05], [0x05, 0x81]),
("0x29 is transmitted as 0x2881", [0x29], [0x28, 0x81]),
(
"0xc001c0de is transmitted as 0xc000711be1",
[0xC0, 0x01, 0xC0, 0xDE],
[0xC0, 0x00, 0x71, 0x1B, 0xE1],
),
(
"six byte message",
[0x47, 0x72, 0x65, 0x61, 0x74, 0x21],
[0x47, 0xB8, 0x99, 0xAC, 0x17, 0xA0, 0x84],
),
(
"seven byte message",
[0x47, 0x72, 0x65, 0x61, 0x74, 0x31, 0x21],
[0x47, 0xB8, 0x99, 0xAC, 0x17, 0xA0, 0xC5, 0x42],
),
(
"eight byte message",
[0xC0, 0x01, 0x13, 0x37, 0xC0, 0xDE, 0x21, 0x21],
[0xC0, 0x00, 0x44, 0x66, 0x7D, 0x06, 0x78, 0x42, 0x21, 0x81],
),
(
"twenty byte message",
[
0x45, 0x78, 0x65, 0x72, 0x63, 0x69, 0x73, 0x6D, 0x20, 0x69, 0x73, 0x20, 0x61, 0x77,
0x65, 0x73, 0x6F, 0x6D, 0x65, 0x21,
],
[
0x44, 0xBD, 0x18, 0xAF, 0x27, 0x1B, 0xA5, 0xE7, 0x6C, 0x90, 0x1B, 0x2E, 0x33, 0x03,
0x84, 0xEE, 0x65, 0xB8, 0xDB, 0xED, 0xD7, 0x28, 0x84,
],
),
]
|> subtests (description, message, expected), description
assert transmit(message) == expected
end
end
test "decode received messages"
[
("empty message", [], Ok([])),
("zero message", [0x00, 0x00], Ok([0x00])),
("0x0300 is decoded to 0x02", [0x03, 0x00], Ok([0x02])),
("0x0581 is decoded to 0x05", [0x05, 0x81], Ok([0x05])),
("0x2881 is decoded to 0x29", [0x28, 0x81], Ok([0x29])),
("first byte has wrong parity", [0x07, 0x00], Err("wrong parity")),
("second byte has wrong parity", [0x03, 0x68], Err("wrong parity")),
("0xcf4b00 is decoded to 0xce94", [0xCF, 0x4B, 0x00], Ok([0xCE, 0x94])),
("0xe2566500 is decoded to 0xe2ad90", [0xE2, 0x56, 0x65, 0x00], Ok([0xE2, 0xAD, 0x90])),
(
"six byte message",
[0x47, 0xB8, 0x99, 0xAC, 0x17, 0xA0, 0x84],
Ok([0x47, 0x72, 0x65, 0x61, 0x74, 0x21]),
),
(
"seven byte message",
[0x47, 0xB8, 0x99, 0xAC, 0x17, 0xA0, 0xC5, 0x42],
Ok([0x47, 0x72, 0x65, 0x61, 0x74, 0x31, 0x21]),
),
(
"last byte has wrong parity",
[0x47, 0xB8, 0x99, 0xAC, 0x17, 0xA0, 0xC5, 0x43],
Err("wrong parity"),
),
(
"eight byte message",
[0xC0, 0x00, 0x44, 0x66, 0x7D, 0x06, 0x78, 0x42, 0x21, 0x81],
Ok([0xC0, 0x01, 0x13, 0x37, 0xC0, 0xDE, 0x21, 0x21]),
),
(
"twenty byte message",
[
0x44, 0xBD, 0x18, 0xAF, 0x27, 0x1B, 0xA5, 0xE7, 0x6C, 0x90, 0x1B, 0x2E, 0x33, 0x03,
0x84, 0xEE, 0x65, 0xB8, 0xDB, 0xED, 0xD7, 0x28, 0x84,
],
Ok([
0x45, 0x78, 0x65, 0x72, 0x63, 0x69, 0x73, 0x6D, 0x20, 0x69, 0x73, 0x20, 0x61, 0x77,
0x65, 0x73, 0x6F, 0x6D, 0x65, 0x21,
]),
),
(
"wrong parity on 16th byte",
[
0x44, 0xBD, 0x18, 0xAF, 0x27, 0x1B, 0xA5, 0xE7, 0x6C, 0x90, 0x1B, 0x2E, 0x33, 0x03,
0x84, 0xEF, 0x65, 0xB8, 0xDB, 0xED, 0xD7, 0x28, 0x84,
],
Err("wrong parity"),
),
]
|> subtests (description, transmission, expected), description
assert receive(transmission) == expected
end
endok calculate transmit sequences (11 cases)
ok decode received messages (15 cases)
test result: ok. 26 passed, 0 failed
How it’s written
Section titled “How it’s written”- Both directions work on a stream of bits rather than shifting a carry between bytes:
bitsanswers a byte’s eight bits most significant first, andfrom_bitsreads a list of bits back as a number,Int.from_digits(bits, 2)!, whoseNonewould mean a digit other than 0 or 1.transmitisIter.flat_map(bits),Iter.chunks(7)and one byte per chunk;receivechecks and strips each byte,Iter.flattens the data bits and reads them back eight at a time. - Bit
iof a byte isbyte >>> (7 - i) &&& 1over0..8. Eachiis 0 to 7, so7 - iis 0 to 7, which>>>takes as aNonNegativeIntcount. A byte with room for its parity bit isdata <<< 1 + parity: the shifts and&&&bind like*, as in Go, so only the shift count needs parentheses. - The last chunk of a message may be short.
transmitpads it to seven bits with zeros fromIter.repeat(0), and its parity is the sum of its bits modulo 2, so padding needs no special case.receivedrops a short last chunk, the padding the sender added. - A byte with odd parity is
Err("wrong parity"), the canonical message, as grains and variable-length-quantity do with their one error.Result.collectstops at the first bad byte. - Bytes are
List<Int>written in hex, as in variable-length-quantity, for the reason its Friction gives. - The transmit and decode groups are one
subteststable each, named by the description column.