This　paper　presents　several　soft　decision　iterative　decoding　schemes　for　physical-layer　network　coding　(PNC)　operated　with　coded　modulation　(CM)　and　bit-interleaved　coded　modulation　(BICM).　With　respect　to　PNC　operated　with　CM,　we　consider　network　coding-based　channel　decoding　(NC-CD)　and　multi-user　complete　decoding　(MUD-NC)　for　PNC　decoding　at　the　relay.　Their　BICM　counterparts　are　XOR-based　channel　decoding　(XOR-CD)　and　MUD-XOR,　respectively.　First,　we　show　that,　when　the　decoding　is　non-iterative,　there　is　a　gap　between　the　BICM　capacities　of　both　XOR-CD　and　MUD-XOR　under　Gray　mapping　and　the　capacities　of　their　CM　counterparts,　NC-CD,　and　MUD-NC.　This　is　in　contrast　to　the　conventional　point-to-point　communication　system,　for　which　the　BICM　capacity　with　Gray　mapping　is　known　to　be　very　close　to　the　CM　capacity,　without　the　need　for　iterative　decoding.　Second,　we　investigate　the　error　performance　of　iteratively　decoded　BICM　XOR-CD　and　MUD-XOR.　Extrinsic　information　transfer　chart　analysis　and　simulation　results　indicate　that　for　these　Graymapped　BICM　PNC　systems,　iterative　decoding　can　achieve　considerable　gains　over　non-iterative　decoding.　Again,　this　is　in　contrast　to　the　Gray-mapped　BICM　point-to-point　communication　system,　for　which　iterative　decoding　provides　little　gain　over　non-iterative　decoding.　We　further　show　that　Gray　mapping　gives　rise　to　best　PNC　rate　for　MUD-XOR　and　XOR-CD　systems　among　several　bits-to-symbol　mappings　under　study.　Overall,　our　results　indicate　that　BICM　PNC　systems　exhibit　different　decoding　behavior　from　conventional　BICM　point-to-point　systems.　This　paper　serves　as　a　first　foray　into　the　investigation　of　this　issue.