Fault attacks (FA) are a type of non-invasive attacks that intentionally inject some fault into the encryption process and analyze a secret key based on faulty intermediate values or faulty ciphertexts. A common way to defend against FA is to use some type of redundancy such as time or hardware redundancy. However, existing redundancy methods can be broken by skipping comparison operations or by using a non-uniform distribution of faulty intermediate values. In this paper, we propose a secure software-based redundancy, named table redundancy, applying different linear and nonlinear transformations to redundant computations of table-based block cipher structures. To reduce the total size of tables and the number of lookup, some outer tables that are not subjected to FA are shared, while the inner tables are protected by table redundancy. The basic idea is that different transformations protecting redundant computations are correctly decoded if the redundant outcomes are combined without faulty values. In addition, this recombination provides infective computations because a faulty byte is likely to propagate its error to other bytes due to the use of 32-bit linear transformations. Our method also provides a stateful feature by which a detected fault randomizes subsequent ciphertexts thereby preventing the key recovery. We demonstrate the proposed method protecting AES-128 against FA and show that a success probability of FA is negligible.