Spinal Codes over BSC: Error Probability Analysis and the Puncturing Design

As a newly invented type of rateless codes, Spinal codes can be capacity-achieving with short message length and thus hold great prospects for the design of Ultra-Reliable Low-Latency Communication (URLLC) systems. However, the error probability of Spinal codes over Binary Symmetric Channel (BSC) in the finite-length regime lacks explicit analysis in the literature, which in turn hinders efforts to the analytical design of high-efficiency associated techniques, such as the puncturing strategy. In this paper, with the bound on the number of erroneous bits in the Maximum Likelihood (ML) decoding result, we derive the asymptotically tight bound on the Bit Error Rate (BER) of Spinal codes over BSC. Based on this result, we then design the optimal puncturing strategy for Spinal codes over BSC by formulating a rate maximization problem under the constraint of low error probability. In addition, we carry out extensive simulations to verify the correctness of the error probability analysis and the effectiveness of the puncturing strategy design.