We analytically diagonalize a discrete-time on-site interacting fermionic cellular automaton in the two-particle sector. Important features of the solutions sensibly differ from those of analogous Hamiltonian models. In particular, we find a wider variety of scattering processes, we have bound states for every value of the total momentum, and there exist bound states also in the free case, where the coupling constant is null.