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:
- Count the number of
1
's in the message - Modulo by \$2^n\$
- Attach the remainder to the message
For example, using three parity bits (n=3) and the message 10110111110110111
:
10110111110110111
-> 131
's- \$13\mod2^3\$ -> 5
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 code-golf, 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
0
s if necessary. That's only clear from the second and last test cases right now (where0
becomes00
before appending and10
becomes0010
before appending respectively). \$\endgroup\$11000
and10100
generate the same parity bits, regardless ofn
. Yet, only two bits have changed. Since all you do is count the number of1
bits, every permutation of a set of bits will generate the same set of parity bits, and you cannot distinguish between them. \$\endgroup\$