29
\$\begingroup\$

Given a binary message, and the number of parity bits, generate the associated parity bits.

A parity bit is a simple form of error detection. It's generated by counting the number of 1's in the message, if it's even attach a 0 to the end, if it's odd attach 1.
That way, if there's a 1-bit error, 3-bit error, 5-bit error, ... in the message, because of the parity-bit you know the message has been altered.
Although if there were an even number of bits altered, the parity stays the same, so you wouldn't know if the message has been changed.
Only 50% of the time you'd know if bits have been altered with one parity bit.

Generate Parity bits

To generate n parity bits for a given binary message:

  1. Count the number of 1's in the message
  2. Modulo by \$2^n\$
  3. Attach the remainder to the message

For example, using three parity bits (n=3) and the message 10110111110110111:

  1. 10110111110110111 -> 13 1's
  2. \$13\mod2^3\$ -> 5
  3. 10110111110110111 with 5 attached (in binary) -> 10110111110110111101

The last three digits act as parity bits.
The advantage with parity bits is, that they can't detect errors only when a multiple of \$2^n\$ bits have been altered (ignoring messages which share the same permutations). With three parity bits, you can't detect errors when 8, 16, 24, 32, 40, ... bits have been altered.
\$(1-\frac{1}{2^n})\%\$ of the time you'd know when bits have been altered, significantly more than with just one parity bit.

Rules

  • Take as input a binary string or a binary array and an integer (0<n, the number of parity bits)
  • Output a binary string/binary array with n parity bits attached
  • The parity bits should be padded with zeros to length n
  • Leading zeros are allowed
  • This is , so the shortest answer wins

Test Cases

[In]:  10110, 1
[Out]: 101101
[In]:  0110101, 2
[Out]: 011010100
[In]:  1011101110, 3
[Out]: 1011101110111
[In]:  0011001100111101111010011111, 4
[Out]: 00110011001111011110100111110010
\$\endgroup\$
9
  • \$\begingroup\$ Are we allowed to take the input formatted as an array? \$\endgroup\$
    – Baby_Boy
    Commented Oct 3, 2022 at 13:25
  • 1
    \$\begingroup\$ @Baby_Boy hmm okay \$\endgroup\$
    – math scat
    Commented Oct 3, 2022 at 13:28
  • 3
    \$\begingroup\$ You may want to specify in your example that the binary of the integer we're appending should be of length \$n\$, with left-padded 0s if necessary. That's only clear from the second and last test cases right now (where 0 becomes 00 before appending and 10 becomes 0010 before appending respectively). \$\endgroup\$ Commented Oct 3, 2022 at 14:44
  • \$\begingroup\$ @KevinCruijssen right \$\endgroup\$
    – math scat
    Commented Oct 3, 2022 at 14:44
  • 7
    \$\begingroup\$ The advantage with parity bits is, that they can't detect errors only when a multiple of $2^n$ bits have been altered. I don't think that is true. Both 11000 and 10100 generate the same parity bits, regardless of n. Yet, only two bits have changed. Since all you do is count the number of 1 bits, every permutation of a set of bits will generate the same set of parity bits, and you cannot distinguish between them. \$\endgroup\$
    – Abigail
    Commented Oct 3, 2022 at 21:54

31 Answers 31

1
2
0
\$\begingroup\$

Retina 0.8.2, 77 bytes

,.+
,$&$*_1,$`
+`0(1*)$
$1
+`_1
11_
(1+)_+,\1*
$1
+`,(1+)\1
,$1@
@1
1
@
0
,1

Try it online! Link includes test cases. Explanation:

,.+
,$&$*_1,$`

Convert n to unary and append a copy of the message.

+`0(1*)$
$1

Delete any 0s in the copy of the message.

+`_1
11_

Calculate 2ⁿ.

(1+)_+,\1*
$1

Reduce the count of 1s modulo 2ⁿ, but add the 2ⁿ back on.

+`,(1+)\1
,$1@
@1
1

Convert the result to binary, but use @ instead of 0 to avoid disrupting the message.

@
0

Replace @s with 0s now that they're unambiguous.

,1

Remove the leading 1 of the binary number and concatenate the rest to the message.

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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