This paper considers discrete-time input reconstruction and state estimation assuming that the system has no invariant zeros, without assuming that the initial condition is known, and without assuming that at least one Markov parameter has full column rank. Algorithms based on the generalized inverse of a block-Toeplitz matrix are given for unknown-input state estimation and simultaneous input reconstruction and state estimation. In both cases, the unknown input is an arbitrary signal. Both algorithms are deadbeat, which means that exact input reconstruction and state estimation are achieved in a finite number of steps. (C) 2019 Elsevier Ltd. All rights reserved.