产生奇偶校验位

Question

给定二进制消息和奇偶校验位数，生成相关的奇偶校验位。

奇偶校验位是一种简单的错误检测形式。它是通过计算消息中1's的数量来生成的，如果它甚至在末尾附加了一个0，如果它是奇数附加1。

那样的话，如果有一个1位错误，3位错误，5位错误，.在消息中，由于奇偶校验位，您知道消息已被更改。

虽然如果修改了偶数位，但奇偶校验保持不变，因此您将不知道消息是否已被更改。

只有50%的时间，你会知道，如果比特已经改变了一个奇偶位。

生成奇偶校验位

要为给定的二进制消息生成n奇偶校验位，请执行以下操作：

1. 在邮件中数一下1's的号码
2. 2^n调制
3. 将剩余部分附加到消息

例如，使用三个奇偶校验位(n=3)和消息10110111110110111：

1. 10110111110110111 -> 13 1's
2. 13\mod2^3 -> 5
3. 10110111110110111附5(二进制) -> 10110111110110111101

最后三位数字充当奇偶位。

奇偶校验位的优点是，只有在修改了多个2^n位(忽略共享相同排列的消息)时，它们才能检测错误。使用三个奇偶校验位，当8、16、24、32、40、.比特已经被改变了。

(1-\frac{1}{2^n})\%

当你知道什么时候位被改变的时候，比仅仅使用一个奇偶校验位要多得多。

规则

• 以二进制字符串或二进制数组和整数(0<n，奇偶位数)作为输入。
• 输出带有n奇偶位的二进制字符串/二进制数组
• 奇偶校验位应以零填充，以长度为n。
• 允许前导零
• 这是密码-高尔夫，所以最短的答案获胜

测试用例

[In]:  10110, 1
[Out]: 101101
[In]:  0110101, 2
[Out]: 011010100
[In]:  1011101110, 3
[Out]: 1011101110111
[In]:  0011001100111101111010011111, 4
[Out]: 00110011001111011110100111110010

Answer 1

马蒂尔，10字节

tsiW\2M&Bh

在网上试试！或验证所有测试用例.

解释

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

Answer 2

因子，62字节

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

在网上试试！

接受输入作为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"

Answer 3

JavaScript (ES6)，53字节

期望(binary_string)(n)并返回另一个二进制字符串。

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

在网上试试！

评论

从右到左构建输出要容易一些。这样，我们就可以在最后一次递归调用中追加输入字符串。

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