According to one embodiment, in a storage device, a selection circuit selects one mapping rule from a plurality of mapping rules in which each of bit labels having a bit length of (n+1) or more is mapped to n M-ary symbols, when M is defined as an integer of 3 or more and n is defined as an integer of or more. A first conversion circuit converts a data block in data into an M-ary symbol sequence using the selected one mapping rule. A second conversion circuit converts the converted M-ary symbol sequence into an M-step pulse width signal. The recording medium records the converted M-step pulse width signal. A readback circuit equalizes the signal read from the recording medium to the M-ary symbol sequence and restores the data.