Polynomial-Time Decodable Codes for Multiple Access Channels

A construction of polynomial-time decodable codes for discrete memoryless multiple access channels (MACs) is proposed based on concatenated codes. Concatenated codes, originally developed by Forney, can achieve any rate below capacity for the single-user discrete memoryless channel while requiring only polynomial-time decoding complexity in the code length. In this letter, Forney's construction together with multi-level concatenation is generalized to MACs. An error exponent for the constructed code is derived, and it is shown that the constructed code can achieve any rate in the capacity region.