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
    Oct 3, 2022 at 13:25
  • 1
    \$\begingroup\$ @Baby_Boy hmm okay \$\endgroup\$
    – math scat
    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\$ Oct 3, 2022 at 14:44
  • \$\begingroup\$ @KevinCruijssen right \$\endgroup\$
    – math scat
    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
    Oct 3, 2022 at 21:54

31 Answers 31

7
\$\begingroup\$

Zsh --extendedglob, 37 bytes

local -Z$2 -i2 n=${1//10#/+1}
<<<$1$n

Try it online!

The -Z$2 flag does the heavy lifting. It automatically % base**$2, and fills in zeroes. EXTENDED_GLOB 10# is equivalent to regex 10*.

\$\endgroup\$
6
\$\begingroup\$

Ruby, 37 36 bytes

->n,d{n+"%0*b"%[d,n.count(?1)%2**d]}

Try it online!

Thanks @dingledooper for -1 byte.

\$\endgroup\$
3
  • \$\begingroup\$ Since the input is a string, you can use #sum for 34 bytes. \$\endgroup\$
    – south
    Oct 3, 2022 at 21:19
  • \$\begingroup\$ 33 bytes \$\endgroup\$ Oct 3, 2022 at 22:27
  • \$\begingroup\$ @dingledooper I thought about it, but it would fail on a string of 48 1's. Thank you for the %0*b anyway, I didn't know that. \$\endgroup\$
    – G B
    Oct 4, 2022 at 5:44
6
\$\begingroup\$

C (clang), 79 \$\cdots\$ 74 62 bytes

p;f(*b,n){for(p=0;*b|n;)printf("%d",*b?*b++&1&&++p:p>>--n&1);}

Try it online!

Saved a 4 a whopping 16 bytes thanks to the man himself Arnauld!!!
Saved a byte thanks to ceilingcat!!!

Inputs a wide char string and an integer.
Outputs the result to stdout.

\$\endgroup\$
3
  • \$\begingroup\$ 64 bytes \$\endgroup\$
    – Arnauld
    Oct 4, 2022 at 1:14
  • \$\begingroup\$ Ah well, let's go back to printf: 62 bytes \$\endgroup\$
    – Arnauld
    Oct 4, 2022 at 1:34
  • \$\begingroup\$ @Arnauld Impressively orchestrated - bravo! :D \$\endgroup\$
    – Noodle9
    Oct 4, 2022 at 8:57
6
\$\begingroup\$

Excel (ms365), 50 47 bytes

-3 Thanks to @EngineerToast

=A1&BASE(MOD(LEN(SUBSTITUTE(A1,0,)),2^B1),2,B1)

enter image description here

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Save 3 bytes by using BASE instead of DEC2BIN and leaving the the last argument in SUBSTITUTE totally blank instead of using "". Result: =A1&BASE(MOD(LEN(SUBSTITUTE(A1,0,)),2^B1),2,B1) \$\endgroup\$ Oct 6, 2022 at 19:51
  • \$\begingroup\$ @EngineerToast brilliant. Not only does this allow for n>10 again, but how on earth have I never tried to leave the 3rd parameter blank in SUBSTITUTE()? :S \$\endgroup\$
    – JvdV
    Oct 7, 2022 at 7:24
  • 1
    \$\begingroup\$ You get so deep into the formula that options don't occur to you. It takes a second set of eyes. TaylorRaine has seen me so many bytes that seem more obvious in retrospect. I'm just glad to have another Excel "programmer" around here. \$\endgroup\$ Oct 7, 2022 at 12:03
5
\$\begingroup\$

Haskell, 60 42 bytes

b!n=b++[mod(sum b`div`2^(n-x))2|x<-[1..n]]

Try it online!

  • saved 3 Bytes thanks to @Unrelated String suggesting using list comprehension.
  • saved 10 Bytes by @xnor by removing a redundant modulo. Please check his answer which is still one byte shorter using a more direct approach.
\$\endgroup\$
2
4
\$\begingroup\$

Vyxal, 11 10 bytes

⌊∑$E%Π⁰↳›J

Try it Online! "11 10 bytes?!" I hear you say. Well you gotta remember that when it comes to doing things with base conversion I don't do the best - so keep that in mind when y'all start giving me golfing suggestions :p

Explained

⌊∑$E%Π⁰↳›J
⌊∑         # Sum of the 1s in the input binary
  $E%      # Modulo'd by 2 to the power of n
     Π     # Converted to binary
      ⁰↳   # Padded with spaces to make sure it's of length n
        ›J # With those spaces replaced with 0s and joined to the original binary input
\$\endgroup\$
1
  • \$\begingroup\$ ∑$E%b⁰∆ZJ with i/o as lists \$\endgroup\$
    – naffetS
    Oct 4, 2022 at 0:57
4
\$\begingroup\$

Factor, 62 bytes

[ dup bin> bit-count pick 2^ mod >bin rot 48 pad-head append ]

Try it online!

Takes input as n msg.

          ! 3 "10110111110110111"
dup       ! 3 "10110111110110111" "10110111110110111"
bin>      ! 3 "10110111110110111" 94135
bit-count ! 3 "10110111110110111" 13
pick      ! 3 "10110111110110111" 13 3
2^        ! 3 "10110111110110111" 13 8
mod       ! 3 "10110111110110111" 5
>bin      ! 3 "10110111110110111" "101"
rot       ! "10110111110110111" "101" 3
48        ! "10110111110110111" "101" 3 48
pad-head  ! "10110111110110111" "101"
append    ! "10110111110110111101"
\$\endgroup\$
4
\$\begingroup\$

Nibbles, 8.5 7.5 bytes (15 nibbles)

:$\<@\``@+^2@+

Input and output both as arrays of 0s and 1s.

             +       # get the sum of arg1,
         +           # and add it to
          ^2         # two to the power of
            @        # arg2,   
      ``@            # convert to binary digits,
     \               # reverse them,
   <@                # take arg2 elements,
  \                  # and reverse them back again
                     # (so the last few steps effectively
                     # pad the binary digits to arg2 digits),
:$                   # finally, append this onto arg1

enter image description here

\$\endgroup\$
4
\$\begingroup\$

MATL, 10 bytes

tsiW\2M&Bh

Try it online! Or verify all test cases.

Explanation

t    % Implicit input: numeric vector. Duplicate
s    % Sum
i    % Input: number, n
W    % 2 raised to that
\    % Modulo
2M   % Push n again
&B   % Binary expansion with specified number of digits
h    % Concatenate horizontally. Implicit display
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 53 bytes

Expects (binary_string)(n) and returns another binary string.

s=>g=(n,k)=>k^n?g(n,-~k)+(~-s.split`1`.length>>k&1):s

Try it online!

Commented

It's a little easier to build the output from right to left. This way, we can just append the input string on the last recursive call.

s =>             // outer function taking the binary string s
g = (n,          // inner recursive function taking n
        k) =>    // and a counter k which is initially undefined
k ^ n ?          // if k is not equal to n:
  g(n, -~k) +    //   do a recursive call with k + 1
  (              //   append one binary digit:
    ~-s.split`1` //     to get the number of 1's, subtract 1 from the length
    .length      //     of the array obtained by splitting the input on 1's
    >> k & 1     //     right shift by k positions and keep the LSB
  )              //
:                // else:
  s              //   append s and stop the recursion
\$\endgroup\$
3
\$\begingroup\$

Python, 48 bytes

lambda a,b:b+bin(b.count("1")%2**a)[2:].zfill(a)

Finally, a use for zfill!

Attempt This Online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 10 bytes

SBŻ⁹¡ṫC}⁸;

A dyadic Link that accepts a list of bits on the left and a positive integer on the right and yields a list of bits extended with the parity bits.

Try it online! Or see the test-suite.

How?

SBŻ⁹¡ṫC}⁸; - Link: bits, n
S          - sum (bits) -> count of ones
 B         - to binary
    ¡      - repeat...
   ⁹       - ...times: chain's right argument = n
  Ż        - ...action: prepend a zero
             -> count of ones as binary with n leading zeros
       }   - using the right argument (n):
      C    -   complement -> 1-n
     ṫ     - tail (from 1-indexed index 1-n)
             -> parity bits (including any necessary leading zeros)
        ⁸  - chain's left argument = bits
         ; - concatenate (parity bits) to (bits)
\$\endgroup\$
3
\$\begingroup\$

Haskell, 41 bytes

l!n=l++cycle(mapM(:[1])$0<$[1..n])!!sum l

Try it online!

Input and output are lists. Test case code from AZTECCO.

Haskell doesn't have built-in binary operations, so we do things by hand. The mapM(:[1])$0<$[1..n] is one shorter than writing mapM(\_->[0,1])[1..n], for taking the n-fold Cartesian product of [0,1]. Applying cycle then lets us modular index into it.

\$\endgroup\$
3
\$\begingroup\$

Rust, 120 117 bytes

  • -3 bytes thanks to JSorngard
|k:Vec<_>,m|k.iter().copied().chain((0..m).rev().map(|j|k.iter().filter(|i|**i).count()&1<<j>0)).collect::<Vec<_>>();

Attempt This Online!

\$\endgroup\$
2
3
\$\begingroup\$

K (ngn/k), 13 bytes

{x,(y#2)\+/x}

Try it online!

Takes input as a list of 0s and 1s (x) and an integer y.

  • +/x the "popcnt" of the input (i.e. the number of set bits)
  • (y#2)\ "encode" the sum (using (y#2) guarantees the length of the result)
  • x, append the parity bits (and implicitly return)
\$\endgroup\$
3
\$\begingroup\$

Python, 44 39 65 40 bytes

m should be a binary string, while n an int.

Had to add 26 bytes all because OP didn't say that 0's had to be prefixed to the parity bits, but doesn't matter since Neil found a shorter solution.

lambda m,n:m+bin(m.count('1')+2**n)[-n:]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ This doesn't work when the number of parity bits is less than n bits long, e.g. "000",3 \$\endgroup\$ Oct 3, 2022 at 14:14
  • \$\begingroup\$ never mind, i've updated it \$\endgroup\$ Oct 3, 2022 at 14:57
  • 1
    \$\begingroup\$ 40 bytes. \$\endgroup\$
    – Neil
    Oct 3, 2022 at 17:46
  • \$\begingroup\$ Also 40 bytes \$\endgroup\$
    – xnor
    Oct 4, 2022 at 5:07
2
\$\begingroup\$

Java 8, 87 73 72 bytes

b->n->b+n.toString((n=1<<n)|n.bitCount(n.valueOf(b,2))%n,2).substring(1)

-14 bytes thanks to @ceilingcat

Try it online.

Explanation:

b->n->                  // Method with String & Integer parameters and String return
  b                     //  Return the given binary-String
   +                    //  Appended with:
    n.toString(         //   Convert the following integer to a (binary-)String:
      (n=1<<n)          //    1 bitwise left-shifted by `n`
                        //    (which is saved in `n` to reuse later on)
      |                 //    Bitwise-ORed by:
       n.bitCount(      //     The amount of 1-bits
        n.valueOf(b,2)) //     in the binary-String input
      %n                //    Modulo the `1<<n` we saved in variable `n`,
                        //    which is basically 2 to the power (input) `n`
      ,2)               //   (Use base-2 for the `n.toString`)
         .substring(1)  //   And remove the leading "1"

n.toString(1<<length|value,2).substring(1) is taken from this Stackoverflow answer.

\$\endgroup\$
0
2
\$\begingroup\$

Charcoal, 14 bytes

Nθη✂⍘⁺X²θΣη²±θ

Try it online! Link is to verbose version of code. Takes n as the first input. Explanation:

Nθ

Input n as a number.

η

Print the binary message.

✂⍘⁺X²θΣη²±θ

Sum the bits in the binary message, add on 2ⁿ, convert to binary, and print the last n digits.

\$\endgroup\$
2
\$\begingroup\$

Acc!!, 149 bytes

N
Count b while _%52/48 {
Write _%52
_+_%52*51-2496+N
}
_+N%4
Count p while _%4 {
Count j while _%4/2*(p-j) {
Write _/52/2^(p-1-j)%2+48
}
_-_%4+N%4
}

Takes input as a binary string, followed by a space, followed by an integer in unary, followed by a newline. Try it online!

Explanation

# Read a character into the accumulator
N
# Since all the characters we'll need to handle have character codes less than 52,
# we can store the most recently read character in _%52 and the number of 1 bits
# in _/52
# While the most recent character code is >= 48 (i.e. a digit):
Count b while _%52/48 {
  # Write that digit
  Write _%52
  # Add 52 to the accumulator (i.e. add 1 to _/52) if the digit was a 1
  _+(_%52-48)*52
  # Clear the previously read character and read a new one
  _-_%52+N
}
# After reading a space, the above loop exits; _/52 is the number of 1 bits
# in the input, while _%52 is 32 from the just-read space
# In the next section, we want to distinguish among three cases:
# - Reading a 1 (code 49) means keep the loop going
# - Reading a newline (code 10) means output the parity bits
# - Reading EOF (code 0) means exit the loop
# These cases can be distinguished by taking the character code mod 4
# Read a character and add its character code mod 4 to the accumulator
_+N%4
# While accumulator mod 4 is not zero, increment p (starting from 0) and:
Count p while _%4 {
  # If accumulator mod 4 is >= 2 (meaning we just read a newline),
  # increment j (starting from 0) and loop while p-j is nonzero:
  Count j while (_%4/2)*(p-j) {
    # Write the jth parity bit, which is the bit in the 2^(p-1-j)'s place of
    # the number of 1 bits (stored in _/52)
    Write (_/52)/2^(p-1-j)%2+48
  }
  # Clear the previously read character (mod 4) and read a new one (mod 4)
  _-_%4+N%4
}
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 12 bytes

DSOIo%bI°+¦«

Inputs in the order \$b,n\$. Binary-I/O as strings.

Try it online or verify all test cases.

Explanation:

D             # Duplicate the first (implicit) input binary-string
 SO           # Sum the digits of the copy
   I          # Push the second input-integer
    o         # Pop and push 2 to the power this input
     %        # Modulo the bit-sum by this
      b       # Convert it to a binary-string
       I      # Push the second input-integer again
        °     # Pop and push 10 to the power this input this time
         +    # Add it to the binary
          ¦   # Remove the leading 1
           «  # Merge the two binary-strings together
              # (after which the result is output implicitly)

If we didn't had to retain the potentially leading 0s of input binary-strings, this could have been 11 bytes with an arithmetic addition approach:

Î׫DSO¹o%b+

Inputs in the order \$n,b\$. Binary-I/O as strings.

Try it online or verify all test cases.

Explanation:

Î            # Push 0 and the first input-integer
 ×           # Repeat the 0 that many times as string
  «          # Append it to the (implicit) input binary-string
   D         # Duplicate it
    SO       # Sum the digits of the copy
      ¹      # Push the first input-integer again
       o     # Pop and push 2 to the power this input
        %    # Modulo the bit-sum by this
         b   # Convert it to binary
          +  # Add the two binary strings together arithmetically
             # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Rust, 88 58 bytes

|a,n|format!("{a}{:0n$b}",(a.split('1').count()-1)%(1<<n))

Try it online!

This closure can be assigned to a variable of type fn(&str,usize) -> String.

Edit: Saved 30 bytes with split('1').count() instead of converting to an integer, as in Joost's answer, thanks!

\$\endgroup\$
2
\$\begingroup\$

Pip, 28 bytes

a.(J(0*,bALTB($+a)%2Eb))@>-b

Try It Online!

Holy crap, this is terrible. There must be a better way to go about this. This 100% golfable.

\$\endgroup\$
1
\$\begingroup\$

Japt -P, 13 bytes

pUx u2pV)¤ù0V

Try it

pUx u2pV)¤ù0V
 Ux            # Sum of the digits in U
    u   )      # Modulo:
     2pV       #   2 to the power of V
         ¤     # Convert to base 2
          ù0V  # Left-pad with 0 until the length is V
p              # Add that string to the end of U
               # Print the array with no delimiter

Can be modified to run without -P for 15 bytes

\$\endgroup\$
1
  • \$\begingroup\$ Pretty much exactly what I had. Although I was taking input as a string and using +è1 instead of pUx, which would allow you to drop the -P flag for the same byte count. \$\endgroup\$
    – Shaggy
    Oct 4, 2022 at 8:40
1
\$\begingroup\$

Pyth, 18 bytes

pz.[\0KE.B%/z\1^2K

Try it online!

Explanation:

pz                    print the first input with no newline
      KE              evaluate the second input and store in K
           /z\1       number of occurrences of "1" in the first input
          %    ^2K    modulo 2 ^ K
        .B            binary representation
  .[\0K               pad with copies of "0" until length K and implicitly print
\$\endgroup\$
1
\$\begingroup\$

Desmos, 58 bytes

f(l,n)=join(l,mod(floor(2mod(l.total,2^n)/2^{[n...1]}),2))

\$f(l,n)\$ takes in a list of bits \$l\$, representing the binary message, and an integer \$n\$, representing the number of parity bits, and returns a list of bits representing the parity bits.

Try It Online

Try It Online - Prettified

\$\endgroup\$
0
1
\$\begingroup\$

PowerShell Core, 77 bytes

param($s,$n)$s
$l=($s-eq1).Count
($u=0..--$n|%{$l%2
$l=$l-shr1})[$n..1]+$u[0]

Try it online!

Takes the binary string as an int array and returns an array of ints

Explanations

$s                             # Returns $s as is
$l=($s-eq1).Count              # Counts the number of ones
$u=0..--$n|%{$l%2;$l=$l-shr1}} # Gets the number as binary inverted (smallest bit on the left)
$u[$n..1]+$u[0]                # Returns the binary representation inverted. The $u[0] is to handle the case where $n=1
\$\endgroup\$
1
\$\begingroup\$

J, 19 bytes

[,(]#2:)#:+/@[|~2^]

Try it online!

This feels golfable, but I can't for the life of me figure out where without an entirely different approach.

Explanation

[,(]#2:)#:+/@[|~2^]     left: binary array. right: parity bit count
          +/@[          sum of bit array (number of 1s)
              |~        modulo
                2^]     2^parity
  (]#2:)                generate a number of 2s equal to parity bit count
        #:              and use them to convert the above quantity to base 2
                        this generates the requisite padding
[,                      concatenate them to the right of the binary array
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 46 bytes

v=>n=>v+(v.split`1`.length-1%2**n).toString(2)

Try it online! it was actually surprisingly easy in javascript

\$\endgroup\$
1
\$\begingroup\$

><>, 88 bytes

0l:3(?v1-@$"0"-:}+$10.
$1-c1.>@@:aap:2(?v$2*
?v:2%$2,:1%-ab+2.>~%1[:2(
l<0v?=gaa
>n<>r]r

Try it online

\$\endgroup\$
1
\$\begingroup\$

[R] 92 bytes

fun=\(s,n)paste0(s,paste(rev(+(intToBits(nchar(gsub("0","",s))%%2^n)[1:n]==1)),collapse=""))

dat <- data.frame(s=sapply(tests, function(z) z[[1]]), n=1:4, out=outs)
dat
#                              s n                              out
# 1                        10110 1                           101101
# 2                      0110101 2                        011010100
# 3                   1011101110 3                    1011101110111
# 4 0011001100111101111010011111 4 00110011001111011110100111110010

mapply(fun, dat$s, dat$n) == dat$out
#                        10110                      0110101                   1011101110 0011001100111101111010011111 
#                         TRUE                         TRUE                         TRUE                         TRUE 
\$\endgroup\$

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.