A communication system, a relay station, a mobile station, a base station, and a method using a network coding scheme are provided. A communication system includes a relay station, a mobile station, and a base station. A relay station includes a message receiving unit to receive a downlink message transmitted from a base station and an uplink message transmitted from a mobile station, a message generation unit to generate a network coded message by coding the downlink message and the uplink message according to a network coding scheme, and a message transmission unit to transmit the network coded message to the base station and the mobile station during the same time slot.