In this paper, we consider the BER analysis of the constellation rearrangement (CoRe), which is not subject to the Gray-encoding constraint for the first transmission. This type of CoRe can be applied in a parallel transmission system such as cooperative relaying networks. Furthermore, it allow us to construct the accumulate constellation, which obtained by separating and rearranging the received symbols over two different frequency bands. Based on this accumulated constellation, we derive the tight bound on the BER of CoRe over Nakagami-m fading channel. We show that the proposed bound is much tighter than the existing loose bound, e.g., Chernoff bound. Especially, for the Rayleigh fading channel, i.e., m=1, we show that our bound is virtually identical to the simulation result over the acceptable range of Eb/No.