Skip to content

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
end
  • Both directions work on a stream of bits rather than shifting a carry between bytes: bits answers a byte’s eight bits most significant first, and from_bits reads a list of bits back as a number, Int.from_digits(bits, 2)!, whose None would mean a digit other than 0 or 1. transmit is Iter.flat_map(bits), Iter.chunks(7) and one byte per chunk; receive checks and strips each byte, Iter.flattens the data bits and reads them back eight at a time.
  • Bit i of a byte is byte >>> (7 - i) &&& 1 over 0..8. Each i is 0 to 7, so 7 - i is 0 to 7, which >>> takes as a NonNegativeInt count. A byte with room for its parity bit is data <<< 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. transmit pads it to seven bits with zeros from Iter.repeat(0), and its parity is the sum of its bits modulo 2, so padding needs no special case. receive drops 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.collect stops 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 subtests table each, named by the description column.