According to an embodiment, a semiconductor memory device includes a nonvolatile memory; an input/output control unit to control input/output of data to/from the nonvolatile memory; an address translation table that associates first address information specifying a logical recording position of user data stored in the nonvolatile memory with second address information indicating a physical recording position in the nonvolatile memory; a translating unit to translate the first address information to the second address information according to the table; and a generating unit to generate redundant data for checking whether there is error in the user data and the first address information used as one data piece. The input/output control unit records, as data set, the user data, the first address information, and the redundant data, which are used as one data set, in the physical recording position in the nonvolatile memory indicated by the second address information.