In practical asynchronous bi-directional relaying, symbols transmitted by two sources cannot arrive at the relay with perfect frame and symbol alignments and the asynchronous multiple-access channel (MAC) should be seriously considered. Recently, Lu et al. proposed a Tanner-graph representation of the symbol-asynchronous MAC with rectangular-pulse shaping and further developed the message-passing algorithm for optimal decoding of the symbol-asynchronous physical-layer network coding. In this paper, we present a general channel model for the asynchronous MAC with arbitrary pulse-shaping. Then, the Bahl, Cocke, Jelinek, and Raviv (BCJR) algorithm is developed for optimal decoding of the asynchronous MAC channel. For Low-Density Parity-Check (LDPC)-coded BPSK signalling over the symbol-asynchronous MAC, we present a formal log-domain generalized sum-product-algorithm (Log-G-SPA) for efficient decoding. Furthermore, we propose to use cyclic codes for combating the frame-asynchronism and the resolution of the relative delay inherent in this approach can be achieved by employing the simple cyclic-redundancy-check (CRC) coding technique. Simulation results demonstrate the effectiveness of the proposed approach.