We outline a theory of symmetry protected topological phases of one-dimensional quantum walks. We assume spectral gaps around the symmetry-distinguished points +1 and -1, in which only discrete eigenvalues are allowed. The phase classification by integer or binary indices extends the classification known for translation invariant systems in terms of their band structure. However, our theory requires no translation invariance whatsoever, and the indices we define in this general setting are invariant under arbitrary symmetric local perturbations, even those that cannot be continuously contracted to the identity. More precisely we define two indices for every walk, characterizing the behavior far to the right and far to the left, respectively. Their sum is a lower bound on the number of eigenstates at +1 and -1. For a translation invariant system the indices add up to zero, so one of them already characterizes the phase. By joining two bulk phases with different indices we get a walk in which the right and left indices no longer cancel, so the theory predicts bound states at +1 or -1. This is a rigorous statement of bulk-edge correspondence. The results also apply to the Hamiltonian case with a single gap at zero.