  This article introduces a novel communication scheme, termed coded compressed
sensing, for unsourced multiple-access communication. The proposed
divide-and-conquer approach leverages recent advances in compressed sensing and
forward error correction to produce a novel uncoordinated access paradigm,
along with a computationally efficient decoding algorithm. Within this
framework, every active device partitions its data into several sub-blocks and,
subsequently, adds redundancy using a systematic linear block code. Compressed
sensing techniques are then employed to recover sub-blocks up to a permutation
of their order, and the original messages are obtained by stitching fragments
together using a tree-based algorithm. The error probability and computational
complexity of this access paradigm are characterized. An optimization
framework, which exploits the tradeoff between performance and computational
complexity, is developed to assign parity-check bits to each sub-block. In
addition, two emblematic parity bit allocation strategies are examined and
their performances are analyzed in the limit as the number of active users and
their corresponding payloads tend to infinity. The number of channel uses
needed and the computational complexity associated with these allocation
strategies are established for various scaling regimes. Numerical results
demonstrate that coded compressed sensing outperforms other existing practical
access strategies over a range of operational scenarios.
